点分治

    科技2025-05-19  7

    #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int N=1e4+10; int h[N],w[N*2],nex[N*2],to[2*N],con=1; int sz[N],ms,rt,sum; int del[N],vis[100000010],dis[N],res[N],ires,m,q[128],ans[128],gc[N],igc; void add(int a,int b,int c) { nex[con]=h[a]; h[a]=con; to[con]=b; w[con++]=c; } int dfs(int now,int fa) { // cout<<now<<endl; sz[now]=1; int tmp=0; for(int i=h[now];i;i=nex[i]) { if(to[i]==fa||del[to[i]]) continue; int mid=dfs(to[i],now); sz[now]+=mid; tmp=max(tmp,mid); } tmp=max(tmp,sum-sz[now]); if(tmp<ms) { ms=tmp; rt=now; } return sz[now]; } void getdis(int now,int fa) { // cout<<now<<endl; res[ires++]=dis[now]; for(int i=h[now];i;i=nex[i]) { if(to[i]==fa||del[to[i]]) continue; dis[to[i]]=dis[now]+w[i]; getdis(to[i],now); } return; } void cal(int now) { igc=0; for(int i=h[now];i;i=nex[i]) { if(del[to[i]]) continue; ires=0; dis[to[i]]=w[i]; getdis(to[i],now); for(int j=0;j<ires;++j) for(int k=0;k<m;++k) { if(q[k]>=res[j]) ans[k]|=vis[q[k]-res[j]]; } for(int j=0;j<ires;++j) { gc[igc++]=res[j]; vis[res[j]]=1; } } for(int i=0;i<igc;++i) vis[gc[i]]=0; } void div(int now) { //cout<<now<<endl; del[now]=vis[0]=1; cal(now); for(int i=h[now];i;i=nex[i]) { if(del[to[i]]) continue; sum=sz[now]; ms=sum; dfs(to[i],0); dfs(rt,0); div(rt); } } int main() { // freopen("1.txt","r",stdin); int n;cin>>n>>m; for(int i=1;i<n;++i) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } for(int i=0;i<m;++i) cin>>q[i]; sum=n; ms=n+1; dfs(1,0); dfs(rt,0); div(rt); for(int i=0;i<m;++i) { if(ans[i]) cout<<"AYE"<<endl; else cout<<"NAY"<<endl; } return 0; }

     

    Processed: 0.011, SQL: 8