题解 CF516D 【Drazil and Morning Exercise】

首先想到 \min f_i 肯定在直径上，于是以该点为根，得到一棵随深度增加 f_i 递增的树。然后对点 u 考虑，如果 u\in S，那么其祖先也可能 \in S，于是一路存下 f_i，向上二分找到刚好符合要求的祖先，用差分给这一段都 +1，取个最大值就是答案了。
以最小的这个点为根还是比较难想的，不过想到了就比较好做了。

#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;
}