[文章目录]
Description
一棵n个点的带权有根树，有p个询问，每次询问树中是否存在一条长度为Len的路径，如果是，输出Yes否输出No。n<=10000,q<=100,len<=1000000
点分治。复杂度qnlogn。
点分治，特别的是每个点统计答案时需要将子树分开考虑，使得所有链中不存在相同的边。然后由于len<1000000。
尝试只统计无重边且通过当前节点的链。方法为:将前面子树的所有深度扔到计数器中。然后将当前深度找询问中的对应的深度，查询计数器。
然后发现需要特判询问0的情况。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 11000
int n,nn,q,ques[110],ans[110];
bool v[1001000];
int head[N],to[N<<1],nxt[N<<1],data[N<<1],cnt;
void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; data[cnt]=z;
}
int msi[N],siz[N],dis[N],cg[N],cgg,root;
bool vis[N];
void getroot(int x,int pre)
{
siz[x]=1; msi[x]=0;
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre&&!vis[to[i]])
{
getroot(to[i],x);
msi[x]=max(msi[x],siz[to[i]]);
siz[x]+=siz[to[i]];
}
msi[x]=max(msi[x],nn-siz[x]);
if(msi[x]<msi[root]) root=x;
}
void dfs(int x,int pre)
{
cg[++cgg]=dis[x];
for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre&&!vis[to[i]])
{
dis[to[i]]=dis[x]+data[i];
dfs(to[i],x);
}
}
void calc(int x)
{
int us=1; cgg=0;
for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]])
{
dis[to[i]]=data[i];
dfs(to[i],x);
for(int j=us;j<=cgg;j++)
{
for(int ii=1;ii<=q;++ii)
if(cg[j]<=ques[ii]&&v[ques[ii]-cg[j]]) ans[ii]=true;
}
for(int j=us;j<=cgg;j++) if(cg[j]<=1000000) v[cg[j]]=1;
us=cgg+1;
}
for(int i=1;i<=cgg;++i) if(cg[i]<=1000000) v[cg[i]]=0;
}
void solve(int x)
{
vis[x]=1; calc(x);
for(int i=head[x];i;i=nxt[i]) if(!vis[to[i]])
{
root=0; nn=siz[to[i]];
getroot(to[i],0);
solve(root);
}
}
int main()
{
scanf("%d%d",&n,&q);
int i,x,y,z;
for(i=1;i!=n;++i)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z); add(y,x,z);
}
for(i=1;i<=q;++i) scanf("%d",ques+i);
for(i=1;i<=q;++i) if(ques[i]==0) ans[i]=1;
msi[0]=1<<30; nn=n; v[0]=1;
getroot(1,0);
solve(root);
for(i=1;i<=q;++i)
{
if(ans[i]) puts("Yes");
else puts("No");
}
return 0;
}