官方网站在哪里,门户网站想要微信登录怎么做,浦江县城乡建设局网站,怎么管理网站的内容吗正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP3806 题目大意
一颗树#xff0c;k个询问#xff0c;求是否存在长度为lil_ili的路径。 解题思路
开个桶就好了#xff0c;点分治不解释。 codecodecode
#includecstdio
#includea…正题
评测记录:https://www.luogu.org/recordnew/lists?uid52918pidP3806 题目大意
一颗树k个询问求是否存在长度为lil_ili的路径。 解题思路
开个桶就好了点分治不解释。 codecodecode
#includecstdio
#includealgorithm
#includecstring
#define N 100010
#define inf 10000000
using namespace std;
struct node{int to,next,w;
}a[N*2];
int n,m,que[1010],ok[inf],tot,sum,num,q[N];
int root,siz[N],f[N],ls[N],st[N],dis[N];
int lon[inf];
bool v[N];
void addl(int x,int y,int w)
{a[tot].toy;a[tot].nextls[x];a[tot].ww;ls[x]tot;
}
void groot(int x,int fa)
{siz[x]1;f[x]0;for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||v[y]) continue;groot(y,x);siz[x]siz[y];f[x]max(f[x],siz[y]);}f[x]max(f[x],sum-siz[x]);if(f[x]f[root]) rootx;
}
void get_dis(int x,int fa)
{st[num]dis[x];for(int ils[x];i;ia[i].next){int ya[i].to;if(yfa||v[y]) continue;dis[y]dis[x]a[i].w;get_dis(y,x);}
}
void calc(int x)
{int p0;for(int ils[x];i;ia[i].next){int ya[i].to;if(v[y]) continue;num0;dis[y]a[i].w;get_dis(y,x);for(int jnum;j;j--)for(int k1;km;k)ok[k]|lon[que[k]-st[j]];for(int jnum;j;j--)q[p]st[j],lon[st[j]]1;}for(int i1;ip;i)lon[q[i]]0;
}
void solve(int x)
{v[x]lon[0]1;calc(x);for(int ils[x];i;ia[i].next){int ya[i].to;if(v[y]) continue;sumsiz[y];f[root0]n;groot(y,0);solve(y);}
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i){int x,y,w;scanf(%d%d%d,x,y,w);addl(x,y,w);addl(y,x,w);}for(int i1;im;i)scanf(%d,que[i]);f[0]n;sumn;groot(1,0);solve(root);for(int i1;im;i)if(ok[i]) printf(AYE\n);else printf(NAY\n);
}
