[点分治]模板

**某个菜鸡的代码** ~~但是因为他写的太菜了所以看不懂所以~~写了个注释。 [菜鸡的主页](https://www.luogu.org/space/show?uid=7019) ```cpp #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #define f(i,a,b) for(int i=a;i<=b;++i) using namespace std; int n,m; struct node{ int u,v,w,next; }p[20000+10];//邻接表 int tot,siz[10000+10],head[10000+10],ans,mn,mxs[10000+10];//mxs表示该点的maxsize int root,num,vis[10000+10],dis[10000+10],bel[10000+10];//bel bool bo[10000000+10]; inline void add(int u,int v,int w){//加边 p[++tot].u=u; p[tot].w=w; p[tot].v=v; p[tot].next=head[u]; head[u]=tot; } inline void dfssiz(int u,int f){ siz[u]=1,mxs[u]=0; for(int i=head[u];i;i=p[i].next){ int v=p[i].v; if(v==f||vis[v])continue; dfssiz(v,u); siz[u]+=siz[v];//累加子树大小 if(siz[v]>mxs[u])mxs[u]=siz[v];//存储最大子树的大小 } } void dfsroot(int rt,int u,int f){ if(siz[rt]-siz[u]>mxs[u])mxs[u]=siz[rt]-siz[u];//如果其他树比当前子树大，就更新 if(mxs[u]<mn)mn=mxs[u],root=u;//判断是否更加适合作为重心 for(int i=head[u];i;i=p[i].next){ int v=p[i].v; if(v==f||vis[v])continue;//如果v点被访问过或者v是u的爸爸，就跳过 dfsroot(rt,v,u); } } void dfsdis(int u,int d,int f,int x){ dis[++num]=d;//存储距离 bel[num]=x;//表示属于第几颗子树 if (f==0) x=1; for (int i=head[u];i;i=p[i].next){ int v=p[i].v; if (f==0) ++x;//计算子树数量 if (v==f||vis[v]) continue; dfsdis(v,d+p[i].w,u,x); } } void calc(int u,int d){ int t=0;num=0; memset(bel,0,sizeof(bel)); dfsdis(u,d,0,0); int i=1,j=num; f(i,1,num) f(j,i+1,num) if(bel[i]!=bel[j]) bo[dis[i]+dis[j]]=1;//如果这个路径经过了根节点，就标记 } void dfs(int u){ mn=n; dfssiz(u,0);//先求一遍size大小 dfsroot(u,u,0);//求重心 calc(root,0);//计算点对距离 vis[root]=1; for(int i=head[root];i;i=p[i].next){ int v=p[i].v; if(vis[v])continue;//如果这个点被访问过就跳过 dfs(v); } } int main(){ int x,y,z,k; scanf("%d%d",&n,&k); f(i,1,n-1){ scanf("%d%d%d",&x,&y,&z); add(x,y,z),add(y,x,z); } dfs(1); f(i,1,k){ scanf("%d",&m); if(bo[m])printf("AYE\n");//判断该长度是否存在 else printf("NAY\n"); } return 0; } ```