LGP9755 [CSP-S 2023] 种树 学习笔记
Luogu Link
前言
故地重游。
巧合的是，上次写这道题刚好是在去年的九月二十七日，整整一年前。
题意简述
给定一个 \(n\) 个点，\(n-1\) 条边的简单无向连通图。
好吧，这片地本身的形态也是一棵树。
你的目标是：在每个结点上种一棵树，使其长到不低于 \(a_i\) 米。
你每天可以选择一个未种树且与已种树结点邻接的结点，种一棵高度为 \(0\) 米的树。若所有地块均已种树，则你当天不进行任何操作。特别地，第一天你只能在 \(1\) 号空地种树。
对每个地块而言，从该地块被种下树的当天开始，该地块上的树每天都会生长一定的高度。由于气候和土壤条件不同，在整个任务的第 \(x\) 天结束时，\(i\) 号地块上的树会长高 \(\max(b_i+x\times c_i,1)\) 米。注意这里的 \(x\) 是从整个任务的第一天，而非种下这棵树的第一天开始计算。
你想知道：最少需要多少天能够完成你的任务？
\(n\le 10^5\)，\(1\le a_i\le 10^{18}\)，\(1\le b_i\le |c_i|\le 10^9\)。保证存在方案能在 \(10^9\) 天内完成任务。
做法解析
显然树越早种下去越好。整个问题是可以二分判断的。
二分时怎么判断呢？我们发现对于某个截止时间，每个结点都有一个最晚需要种树的时间点 \(lst_u\)，这东西也是可以二分求的。除此之外，\(lst_u\) 也要对 \(lst_v-1\) 取最小值。最后你从 \(1\) 开始贪心地选最急迫的结点就行了。
在二分 \(lst_u\) 的时候你会需要计算 \(\sum_{i=l}^r\max(b_i+x\times c_i,1)\)。
\(c_i\ge 0\) 的情况是好求的（题目保证了 \(b_i\ge 1\) 很舒服，我们不用考虑 \(b_i+x\times c_i\) 单增但不恒大于 \(1\) 的可能性）。
对于 \(c_i<0\) 的情况你需要先解一下 \(b_i+x\times c_i\ge 1\) 这个不等式。由于负数取模取整很麻烦，我们选择将其移项为 \(-c_i\times x\le b_i-1\)，得 \(x\le\lfloor\frac{b_i-1}{-c_i}\rfloor\)。然后分段计算即可。
这样我们就在 \(O(n\log V\log n)\) 的时间复杂度内解决了此问题。
代码实现
注意会出现 \(V_c\times n^2\) 规模的运算，所以 calc 里面记得该开 __int128 的地方要开。
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=1e5+5;
int N,X,Y;lolo A[MaxN],B[MaxN],C[MaxN];
vector<int> Tr[MaxN];
void addudge(int u,int v){Tr[u].push_back(v);Tr[v].push_back(u);
}
molo calc(int u,lolo lb,lolo rb){if(C[u]>=0)return B[u]*(rb-lb+1)+(lb+rb)*(rb-lb+1)/2*molo(1)*C[u];int bkp=(B[u]-1)/-C[u];if(bkp<lb)return rb-lb+1;if(rb<=bkp)return B[u]*(rb-lb+1)+(lb+rb)*(rb-lb+1)/2*molo(1)*C[u];return B[u]*(bkp-lb+1)+(rb-bkp)+(lb+bkp)*(bkp-lb+1)/2*molo(1)*C[u];
}
int lst[MaxN];
int getlst(int u,int lim){int sl=1,sr=N,smid,res=0;while(sl<=sr){smid=(sl+sr)>>1;if(calc(u,smid,lim)>=A[u])res=smid,sl=smid+1;else sr=smid-1;}return res;
}
void dfs(int u,int f){for(int v : Tr[u]){if(v==f)continue;dfs(v,u),minner(lst[u],lst[v]-1);}
}
bool solve(int lim){for(int i=1;i<=N;i++){lst[i]=getlst(i,lim);if(!lst[i])return false;}dfs(1,0);sort(lst+1,lst+N+1);for(int i=1;i<=N;i++)if(lst[i]<i)return false;return true;
}
int main(){readi(N);for(int i=1;i<=N;i++)readis(A[i],B[i],C[i]);for(int i=1;i<N;i++)readis(X,Y),addudge(X,Y);int sl=N,sr=1e9,smid,ans;while(sl<=sr){smid=(sl+sr)>>1;if(solve(smid))ans=smid,sr=smid-1;else sl=smid+1;}writi(ans);return 0;
}