题目传送门
分析:
点分治板题, 对于每个重心, set 维护每个子树里面的路径, 然后每添加一棵子树的值之前, 询问一下 set 里面是否有 Len-dis[i] 即可
找到了就不做了, 可以变很快
注意询问的 Len 可能为 0
- #include<cstdio>
- #include<cstring>
- #include<cmath>
- #include<algorithm>
- #include<vector>
- #include<queue>
- #include<set>
- #define maxn 20005
- using namespace std;
- inline int getint()
- {
- int num=0,flag=1;char c;
- while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;
- while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();
- return num*flag;
- }
- int n,q,K,rt,N;
- int fir[maxn],nxt[maxn],to[maxn],len[maxn],cnt;
- int qq[maxn];
- int sz[maxn];
- bool vis[maxn];
- int a[maxn],cur,dis[maxn];
- set<int>S;
- set<int>::iterator it;
- bool ans[maxn];
- inline void newnode(int u,int v,int w)
- {to[++cnt]=v,nxt[cnt]=fir[u],fir[u]=cnt,len[cnt]=w;}
- inline void getrt(int u,int fa)
- {
- sz[u]=1;
- int mx=0;
- for(int i=fir[u];i;i=nxt[i])
- if(to[i]!=fa&&!vis[to[i]])
- {
- getrt(to[i],u);
- sz[u]+=sz[to[i]];
- mx=max(mx,sz[to[i]]);
- }
- mx=max(mx,N-sz[u]);
- if(mx<=N/2)rt=u;
- }
- inline void dfs(int u,int fa)
- {
- sz[u]=1;
- for(int i=fir[u];i;i=nxt[i])
- if(to[i]!=fa&&!vis[to[i]])
- dfs(to[i],u),sz[u]+=sz[to[i]];
- }
- inline void cal(int rt)
- {
- S.clear();S.insert(0);
- for(int i=fir[rt];i;i=nxt[i])
- if(!vis[to[i]])
- {
- cur=0;
- queue<int>Q;
- dis[to[i]]=len[i];
- Q.push(to[i]);a[++cur]=dis[to[i]];
- while(!Q.empty())
- {
- int u=Q.front();Q.pop();
- for(int j=fir[u];j;j=nxt[j])
- if(sz[u]>sz[to[j]])
- dis[to[j]]=dis[u]+len[j],Q.push(to[j]),a[++cur]=dis[to[j]];
- }
- for(int k=1;k<=q;k++)if(!ans[k])for(int j=1;j<=cur;j++)if(S.find(qq[k]-a[j])!=S.end())ans[k]=1;
- for(int j=1;j<=cur;j++)S.insert(a[j]);
- }
- }
- inline void solve(int u)
- {
- for(int i=fir[rt];i;i=nxt[i])
- if(!vis[to[i]])
- {
- N=sz[to[i]];
- getrt(to[i],to[i]);
- dfs(rt,rt),cal(rt),vis[rt]=1;
- solve(to[i]);
- }
- }
- int main()
- {
- n=getint(),q=getint();
- for(int i=1;i<n;i++)
- {
- int u=getint(),v=getint(),w=getint();
- newnode(u,v,w),newnode(v,u,w);
- }
- for(int i=1;i<=q;i++)qq[i]=getint();
- N=n;getrt(1,1);
- dfs(rt,rt),cal(rt);vis[rt]=1;
- solve(rt);
- for(int i=1;i<=q;i++)
- if(!qq[i]||ans[i])printf("Yes\n");
- else printf("No\n");
- }
来源: http://www.bubuko.com/infodetail-3399999.html