令$f_{k}$为离$k$最远的点到$k$的距离，任取树的一条直径$(x,y)$，有$f_{k}=\max(dis(k,x),dis(k,y))$

更进一步的，取直径中点$mid$（这里定义为$f_{mid}$最小的点，有多个任取一点）并以其为根建树，则所有节点儿子的$f$不小于父亲的$f$

根据这个性质，枚举这个连通块的根$k$（也可以说是连通块内$f$最小的点），即统计其子树内权值在$[f_{k},f_{k}+l]$中的点数量，但可持久化线段树去维护会TLE

事实上，这个还有一种比较巧妙地方式计算：

将所有$f$从大到小排序，依次枚举$k$，去计算$k$子树内权值在$[f_{k},f_{k}+l]$的点

通过单调性，在左边删除、右边加入可以维护出在排序后的对应区间，现在将这个区间内的所有点的导出子图用并查集去维护，那么所求的也就是$k$子树大小

关于如何维护并查集，也就是要支持插入和删除，插入将其树上所有儿子都与其合并，删除的节点必然是导出子图上的叶子，直接删除即可

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define N 100005
  4 #define ll long long
  5 #define fi first
  6 #define se second
  7 struct Edge{
  8     int nex,to,len;
  9 }edge[N<<1];
 10 int V,E,n,m,x,y,z,head[N],sh[N],f[N][21],fa[N],sz[N];
 11 ll l,dep[N];
 12 pair<ll,int>ans[N];
 13 int find(int k){
 14     if (k==fa[k])return k;
 15     return fa[k]=find(fa[k]);
 16 }
 17 void merge(int x,int y){
 18     x=find(x),y=find(y);
 19     if (x!=y){
 20         fa[x]=y;
 21         sz[y]+=sz[x];
 22     }
 23 }
 24 void add(int x,int y,int z){
 25     edge[E].nex=head[x];
 26     edge[E].to=y;
 27     edge[E].len=z;
 28     head[x]=E++;
 29 }
 30 int lca(int x,int y){
 31     if (sh[x]<sh[y])swap(x,y);
 32     for(int i=20;i>=0;i--)
 33         if (sh[f[x][i]]>=sh[y])x=f[x][i];
 34     if (x==y)return x;
 35     for(int i=20;i>=0;i--)
 36         if (f[x][i]!=f[y][i]){
 37             x=f[x][i];
 38             y=f[y][i];
 39         }
 40     return f[x][0];
 41 }
 42 ll dis(int x,int y){
 43     return dep[x]+dep[y]-2*dep[lca(x,y)];
 44 }
 45 void pre_diam(int k,int fa,ll s){
 46     dep[k]=s;
 47     for(int i=head[k];i!=-1;i=edge[i].nex)
 48         if (edge[i].to!=fa)pre_diam(edge[i].to,k,s+edge[i].len);
 49 }
 50 void pre_lca(int k,int fa,ll s,int ss){
 51     sh[k]=ss;
 52     dep[k]=s;
 53     f[k][0]=fa;
 54     for(int i=1;i<=20;i++)f[k][i]=f[f[k][i-1]][i-1];
 55     for(int i=head[k];i!=-1;i=edge[i].nex)
 56         if (edge[i].to!=fa)pre_lca(edge[i].to,k,s+edge[i].len,ss+1);
 57 }
 58 void pre_son(int k,int fa){
 59     f[k][0]=fa;
 60     for(int i=head[k];i!=-1;i=edge[i].nex)
 61         if (edge[i].to!=fa)pre_son(edge[i].to,k);
 62 }
 63 int main(){
 64     scanf("%d",&n);
 65     memset(head,-1,sizeof(head));
 66     for(int i=1;i<n;i++){
 67         scanf("%d%d%d",&x,&y,&z);
 68         add(x,y,z);
 69         add(y,x,z);
 70     }
 71     pre_diam(1,0,0);
 72     x=1;
 73     for(int i=2;i<=n;i++)
 74         if (dep[i]>dep[x])x=i;
 75     pre_diam(x,0,0);
 76     y=1;
 77     for(int i=2;i<=n;i++)
 78         if (dep[i]>dep[y])y=i;
 79     pre_lca(1,1,0,0);
 80     for(int i=1;i<=n;i++)ans[i]=make_pair(max(dis(x,i),dis(y,i)),i);
 81     sort(ans+1,ans+n+1);
 82     pre_son(ans[1].se,0);
 83     scanf("%d",&m);
 84     for(int i=1;i<=m;i++){
 85         scanf("%lld",&l);
 86         int max_ans=0;
 87         for(int j=1;j<=n;j++){
 88             fa[j]=j;
 89             sz[j]=1;
 90         }
 91         for(int j=n,k=n;j;j--){
 92             for(int t=head[ans[j].se];t!=-1;t=edge[t].nex)
 93                 if (edge[t].to!=f[ans[j].se][0])merge(ans[j].se,edge[t].to);
 94             while (ans[k].fi>ans[j].fi+l){
 95                 sz[find(ans[k].se)]--;
 96                 k--;
 97             }
 98             max_ans=max(max_ans,sz[find(ans[j].se)]);
 99         }
100         printf("%d\n",max_ans);
101     }
102 }

View Code