点分治是一种基于分治的算法
整体思想为不断删根把一棵较大的树拆成n个小树再分别求解再合并
关于此题
我们先随意指定一个根，树上路径就分成了过根的和不过根在一个子树里的
这样经过根的路径即为dis[u]+dis[v],dis[i]是i到根的路径长度
不经过根的就再找这棵子树的根如此递归
显然分治
把一个无根树转化为有根树，找重心
void getrt(int u,int fa){//找根 sz[u]=1;maxp[u]=0; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(v==fa||vis[v])continue; getrt(v,u); sz[u]+=sz[v]; maxp[u]=max(maxp[u],sz[v]); } maxp[u]=max(maxp[u],sum-sz[u]); if(maxp[u]<maxp[rt])rt=u; }
找重心的意义在于每次选取子树的重心为子树的树根进行处理， 这样总的递归深度不会超过logN层
以保证复杂度
预处理
void calc(int u){ int p=0; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(vis[v])continue; rem[0]=0; dis[v]=e[i].w; getdis(v,u);//处理u的每个子树的dis for(int j=rem[0];j;j--)//遍历当前子树的dis for(int k=1;k<=m;k++){//遍历每个询问 if(query[k]>=rem[j])//如果query[k]-rem[j]d的路径存在就标记第k个询问 test[k]|=ju[query[k]-rem[j]]; //如果query[k]-rem[j]d的路径存在就标记第k个询问 } for(int j=rem[0];j;j--){//保存出现过的dis于judge q[++p]=rem[j]; ju[rem[j]]=1; } } for(int i=1;i<=p;i++){ ju[q[i]]=0; } }
总复杂度O(NmlogN)
// // main.cpp // 【模版】点分治 // // Created by gengyf on 2019/7/11. // Copyright © 2019 yifan Geng. All rights reserved. // //洛谷P3086 /* 给定一棵有n个点的树 询问树上距离为k的点对是否存在。 input n,m 接下来n-1条边a,b,c描述a到b有一条长度为c的路径 接下来m行每行询问一个K output 对于每个K每行输出一个答案，存在输出“AYE”,否则输出”NAY”(不包含引号) */ #include <bits/stdc++.h> using namespace std; const int inf=10000000; const int maxn=100010; int n,m,sum,rt,ans; struct edge{ int nxt,to,w; }e[maxn*2]; int cnt,head[maxn]; int maxp[maxn],sz[maxn],dis[maxn],rem[maxn]; //maxp[u]表示删除结点u后产生的子树中,最大的那棵的大小;sz[u]是以u为根的子树大小 //dis[u]表示结点u到根节点rt的路径长度,u到v的路径长即为dis[u]+dis[v] //rem记录从当前根u出发向其中一个子树vi走能够得到的不同距离disint vis[maxn],test[inf],ju[inf],q[maxn]; //vis是用来处理子树中的重心的 //judge[i]表示到根距离为i的路径是否存在 int query[1010];//离线 void add(int from,int to,int w){ e[++cnt].to=to;e[cnt].nxt=head[from];e[cnt].w=w;head[from]=cnt; } //sum是当前子树的总结点数 void getrt(int u,int fa){//找根 sz[u]=1;maxp[u]=0; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(v==fa||vis[v])continue; getrt(v,u); sz[u]+=sz[v]; maxp[u]=max(maxp[u],sz[v]); } maxp[u]=max(maxp[u],sum-sz[u]); if(maxp[u]<maxp[rt])rt=u; } void getdis(int u,int fa){ rem[++rem[0]]=dis[u]; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(v==fa||vis[v])continue; dis[v]=dis[u]+e[i].w; getdis(v,u); } } void calc(int u){ int p=0; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(vis[v])continue; rem[0]=0; dis[v]=e[i].w; getdis(v,u);//处理u的每个子树的dis for(int j=rem[0];j;j--)//遍历当前子树的dis for(int k=1;k<=m;k++){//遍历每个询问 if(query[k]>=rem[j])//如果query[k]-rem[j]d的路径存在就标记第k个询问 test[k]|=ju[query[k]-rem[j]]; //如果query[k]-rem[j]d的路径存在就标记第k个询问 } for(int j=rem[0];j;j--){//保存出现过的dis于judge q[++p]=rem[j]; ju[rem[j]]=1; } } for(int i=1;i<=p;i++){//处理完这个子树就清空judge ju[q[i]]=0; } } void solve(int u){ vis[u]=ju[0]=1; calc(u); for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(vis[v])continue; sum=sz[v]; maxp[rt=0]=inf; getrt(v,0); solve(rt);//在子树中找重心并递归处理 } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<n;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w);add(v,u,w); } for(int i=1;i<=m;i++){ scanf("%d",&query[i]); } maxp[rt]=sum=n; getrt(1,0); solve(rt); for(int i=1;i<=m;i++){ if(test[i])printf("AYE "); else printf("NAY "); } return 0; }