题解 CF516D 【Drazil and Morning Exercise】
VenusM1nT
2020-09-26 21:54:36
首先想到 $\min f_i$ 肯定在直径上，于是以该点为根，得到一棵随深度增加 $f_i$ 递增的树。然后对点 $u$ 考虑，如果 $u\in S$，那么其祖先也可能 $\in S$，于是一路存下 $f_i$，向上二分找到刚好符合要求的祖先，用差分给这一段都 $+1$，取个最大值就是答案了。
以最小的这个点为根还是比较难想的，不过想到了就比较好做了。
```cpp
#include<bits/stdc++.h>
#define N 100000
#define reg register
#define inl inline
#define int long long
#define inf 1e18
using namespace std;
int cnt,fst[N+5],nxt[N*2+5],to[N*2+5],w[N*2+5];
int n,Q,S,T,ans,root=1,dis[N+5],disa[N+5],disb[N+5],f[N+5];
vector <int> val,pos;
inl void AddEdge(reg int u,reg int v,reg int c)
{
to[++cnt]=v;
nxt[cnt]=fst[u];
fst[u]=cnt;
w[cnt]=c;
}
void Dfs1(reg int u,reg int pre,reg int d[])
{
for(reg int i=fst[u];i;i=nxt[i])
{
reg int v=to[i];
if(v==pre) continue;
d[v]=d[u]+w[i];
Dfs1(v,u,d);
}
}
void Dfs(reg int u,reg int pre,reg int x)
{
val.push_back(dis[u]); pos.push_back(u);
f[u]=1; f[pos[lower_bound(val.begin(),val.end(),dis[u]-x)-val.begin()-1]]--;
for(reg int i=fst[u];i;i=nxt[i])
{
reg int v=to[i];
if(v==pre) continue;
Dfs(v,u,x);
f[u]+=f[v];
}
ans=max(ans,f[u]);
val.pop_back(); pos.pop_back();
}
signed main()
{
scanf("%lld",&n);
for(reg int i=1;i<n;i++)
{
reg int x,y,z;
scanf("%lld %lld %lld",&x,&y,&z);
AddEdge(x,y,z);
AddEdge(y,x,z);
}
Dfs1(1,0,disa);
for(reg int i=1;i<=n;i++) if(disa[i]>disa[S]) S=i;
memset(disa,0,sizeof(disa));
Dfs1(S,0,disa);
for(reg int i=1;i<=n;i++) if(disa[i]>disa[T]) T=i;
Dfs1(T,0,disb);
for(reg int i=1;i<=n;i++)
{
dis[i]=max(disa[i],disb[i]);
if(dis[i]<dis[root]) root=i;
}
val.push_back(-inf); pos.push_back(0);
scanf("%lld",&Q);
while(Q--)
{
reg int x;
scanf("%lld",&x);
ans=0;
Dfs(root,0,x);
printf("%lld\n",ans);
}
return 0;
}
```