1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
| #include<bits/stdc++.h> #define REG register #define MAXN 100005 #define LL long long using namespace std; inline void read(int& x){ static char c; while(!isdigit(c=getchar()));x=c^48; while(isdigit(c=getchar()))x=(x*10)+(c^48); } inline void read(LL& x){ static char c; while(!isdigit(c=getchar()));x=c^48; while(isdigit(c=getchar()))x=(x*10)+(c^48); }
inline int Max(int a,int b){return a>b?a:b;} inline LL Max(LL a,LL b){return a>b?a:b;} inline void Swap(int& a,int& b){int t=a;a=b,b=t;} inline void Swap(LL& a,LL& b){LL t=a;a=b,b=t;}
int n,q,Ans; LL DownFir[MAXN],DownSec[MAXN],Up[MAXN],D[MAXN]; int Fa[MAXN],Siz[MAXN],Vis[MAXN];
struct Edge{int v,nxt,w;}ed[MAXN<<1]; int head[MAXN],cnt; inline void adde(int u,int v,int w){ed[++cnt]=(Edge){v,head[u],w},head[u]=cnt;} inline void add(int u,int v,int w){adde(u,v,w),adde(v,u,w);} #define FORE(i,Now) for(REG int i=head[Now];i;i=ed[i].nxt)
struct Node{int Id;LL D;}Srt[MAXN]; inline bool cmp1(const Node& a,const Node& b){return a.D>b.D;} inline bool cmp2(const Node& a,const Node& b){return a.Id<b.Id;}
inline void Update(int Now,int v,int w){ DownSec[Now]=Max(DownSec[Now],DownFir[v]+w); if(DownSec[Now]>DownFir[Now]) Swap(DownSec[Now],DownFir[Now]); }
void DfsDown(int Now,int fa){ FORE(i,Now){ int v=ed[i].v; if(v==fa) continue; DfsDown(v,Now); Update(Now,v,ed[i].w); } }
void DfsUp(int Now,int fa){ D[Now]=Max(DownFir[Now],Up[Now]); FORE(i,Now){ int v=ed[i].v; if(v==fa) continue; Up[v]=ed[i].w+Max(Up[Now],((DownFir[v]+ed[i].w)^DownFir[Now])?DownFir[Now]:DownSec[Now]); DfsUp(v,Now); } }
int GetFa(int Now){return Now==Fa[Now]?Now:Fa[Now]=GetFa(Fa[Now]);}
inline void Union(int x,int y){ int Fx=GetFa(x),Fy=GetFa(y); if(Fx==Fy) return; if(Siz[Fx]<Siz[Fy]) Swap(x,y); Siz[Fx]+=Siz[Fy],Fa[Fy]=Fx; Ans=Max(Ans,Siz[Fx]); }
inline void Work(){ read(n); int u,v,w; for(REG int i=1;i<n;++i) read(u),read(v),read(w),add(u,v,w); DfsDown(1,1),DfsUp(1,1); for(REG int i=1;i<=n;++i) Srt[i]=(Node){i,D[i]}; sort(Srt+1,Srt+n+1,cmp1); read(q); while(q--){ for(REG int i=1;i<=n;++i) Fa[i]=i,Siz[i]=1,Vis[i]=0; LL del; read(del); int l=1,r=1;Ans=0; while(l<=n){ int Now=Srt[l].Id; while(Srt[r].D>Srt[l].D+del) --Siz[GetFa(Srt[r].Id)],++r; Vis[Now]=1; FORE(i,Now){ int v=ed[i].v; if(Vis[v]) Union(Now,v); } ++l; } printf("%d\n",Ans); } }
int main(){Work();}
|