Lvat_s Blog

考虑点分治

一棵一棵子树处理

用set判断一下有没有与len相等的值就可以了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
 
const int N=10005,INF=2100000000;
 
int n,p,len[N],h[N],en,siz[N],vis[N],mx[N],val,root,ans[N],cnt;
long long dis[N*105];
set<long long> St;
 
struct Edge{
int b,next;
long long v;
}e[2*N];
 
void AddEdge(int sa,int sb,long long sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
 
void DfsSiz(int u,int fa){
siz[u]=1;mx[u]=0;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(fa!=v && !vis[v]){
        DfsSiz(v,u);
        siz[u]+=siz[v];
        mx[u]=max(mx[u],siz[v]);
    }
}
}
 
void DfsRoot(int point,int u,int fa){
mx[u]=max(mx[u],siz[point]-mx[u]);
if(val>mx[u]){val=mx[u];root=u;}
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa && !vis[v])DfsRoot(point,v,u);
}
}
 
void Cal(int u,int fa,long long val){
for(int i=1;i<=p;i++)if(St.find(len[i]-val)!=St.end())ans[i]=1;
dis[++cnt]=val;
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(v!=fa & !vis[v])Cal(v,u,val+e[i].v);
}
}
 
void DFS(int u){
val=INF;
DfsSiz(u,u);
DfsRoot(u,u,0);
St.clear();
St.insert(0);
//printf("Root:%d\n",root);
vis[root]=1;
for(int i=h[root];i;i=e[i].next){
    int v=e[i].b;
    if(!vis[v]){
        cnt=0;
        //printf("%d %d\n",cnt,v);
        Cal(v,v,e[i].v);
        for(int j=1;j<=cnt;j++){St.insert(dis[j]);/*printf("%d\n",dis[j]);*/}
    }
}
for(int i=h[root];i;i=e[i].next){
    int v=e[i].b;
    if(!vis[v])DFS(v);
}
}

int main(){
freopen("1316.in","r",stdin);
freopen("1316.out","w",stdout);
scanf("%d %d",&n,&p);
for(int i=1;i<n;i++){
    int u,v,w;
    scanf("%d %d %d",&u,&v,&w);
    AddEdge(u,v,w);
    AddEdge(v,u,w);
}
for(int i=1;i<=p;i++)scanf("%d",&len[i]);
DFS(1);
for(int i=1;i<=p;i++)puts(ans[i]||!len[i]?"Yes":"No");
return 0;
}