本来看一眼点分治，感觉点分治不太想写，所以去写 $dsu on tree$....
但是为了保留儿子的信息就不能维护当前节点到儿子节点的距离，只能维护根到各个节点的距离
而且还不能因为距离大于询问距离就不存了，因为相减后可能会等于
然后因为距离太大所以只能 $map$ 维护，然后就 $T$ 飞了...
所以还是好好写点分治吧......
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+7,M=1e6+7,INF=1e9+7; int n,m,Qmax,q[N],ans[N]; int fir[N],from[N<<1],to[N<<1],val[N<<1],cntt; inline void add(int a,int b,int c) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c; } int sz[N],mx[N],tot,rt; bool vis[N]; void find_rt(int x,int fa) { mx[x]=0; sz[x]=1; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(v==fa||vis[v]) continue; find_rt(v,x); sz[x]+=sz[v]; mx[x]=max(mx[x],sz[v]); } mx[x]=max(mx[x],tot-sz[x]); if(mx[x]<mx[rt]) rt=x; } int T[M],st[N],Top,d[N],dd; void dfs(int x,int fa,ll dis) { if(dis>Qmax) return; st[++Top]=dis; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(v==fa||vis[v]) continue; dfs(v,x,dis+val[i]); } } void work(int x) { T[0]=1; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(vis[v]) continue; Top=0; dfs(v,x,val[i]); for(int j=1;j<=Top;j++) { int d=st[j]; for(int k=1;k<=m;k++) if(q[k]>=d && T[q[k]-d]) ans[k]=1; } for(int j=1;j<=Top;j++) T[st[j]]=1,d[++dd]=st[j]; } for(int i=1;i<=dd;i++) T[d[i]]=0; dd=0; } void solve(int x) { vis[x]=1; work(x); for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(vis[v]) continue; tot=sz[v]; rt=0; find_rt(v,0); solve(rt); } } int main() { mx[0]=INF; n=read(),m=read(); int a,b,c; for(int i=1;i<n;i++) { a=read(),b=read(),c=read(); add(a,b,c); add(b,a,c); } for(int i=1;i<=m;i++) q[i]=read(),Qmax=max(Qmax,q[i]); tot=n; find_rt(1,0); solve(rt); for(int i=1;i<=m;i++) { if(ans[i]||!q[i]) printf("Yes "); else printf("No "); } return 0; }