2023.4.21【图论】点分治
（点分治其实是广泛地统计树上全局路径问题的算法，此处采用luogu模板题的题面）
题目描述
给定一棵有 \(n\) 个点的树，询问树上距离为 \(k\) 的点对是否存在。
- 对于 \(100\%\) 的数据，保证 \(1 \leq n\leq 10^4\)，\(1 \leq m\leq 100\)，\(1 \leq k \leq 10^7\)，\(1 \leq u, v \leq n\)，\(1 \leq w \leq 10^4\)。
算法描述
点分治，又名淀粉质，是计算树上路径问题的算法，与树剖不同的是，它计算的是对于整棵树的所有路径的情况，树剖难以完成。此题有\(m \leq 100\)个询问，我们考虑每一条路径，发现当我们枚举一个点\(x\)时，一条路径要么是经过\(x\)的，要么是与\(x\)不相交的。对于那些与x不相交的路径，我们可以向下分治来讨论。
我们发现，对于过x，但是同时经过x的父亲的路径，在\(x\)的父亲一层会考虑，所以我们只讨论\(x\)的子树以内的路径，遍历每一棵\(x\)的子树（直接连接的儿子），计算子树中每一个数到\(x\)的距离\(dis\)，将它们推进一个桶\(judge\)中，为了方便处理，我们将这个子树的点的\(dis\)在遍历时推进一个队列，我们扫描队列中的每个元素，如果\(judge[k_i - dis]\)是存在的，那么说明存在一条长为\(k\)的路径，从\(x\)先前的子树向上到\(x\)，再向下转到当前子树中的点，这个询问就有答案，鉴于询问数\(m \leq 100\)，直接枚举每个\(k_i\)，然后用\(O(1)\)判断每个\(k_i\)是否可以成立即可（这个地方开桶有一种空间换时间的思想）。对于每次清空\(judge\)数组，不能直接memset,要记录你更改了哪些值，再改回去就好了。
这是计算(calc)函数：
inline void calc(int x)
{
top = 0;
for(int i = head[x];i;i = e[i].next)
{
int to = e[i].v;
if(vis[to]) continue;
dis[to] = e[i].w;
rem[0] = 0;//rem[0]是计数器，rem是队列
getdis(to,x);
for(int j = 1;j <= rem[0];j++)
for(int k = 1;k <= m;k++)
if(query[k] - rem[j] >= 0)
if(judge[query[k] - rem[j]] == 1)
rt[k] = 1;
for(int j = 1;j <= rem[0];j++)
if(rem[j] <= T)
q[++top] = rem[j],judge[rem[j]] = 1;
}
for(int i = 1;i <= top;i++) judge[q[i]] = 0;
}
时间复杂度\(O(nm\ logn)\)
讲解视频：https://www.bilibili.com/video/BV1GJ411x7h7
上条链不久被卡死了qwq
这里需要打破传统的树形问题的遍历顺序，而是每次处理一棵子树时，以这棵子树的重心为根进行处理，这样就能保证把子树切开后，大小一定会小于原来的\(\frac 12\)，所以就能保证复杂度严格，但是遍历顺序改变了，所以遍历过的点要将一个\(vis\)标签打为1，在所有函数的遍历中，如果\(vis_{son} = 1\)，就不访问\(son\)。
找重心部分：（一个点为根子树大小的最大值最小）
inline void dfs(int x,int last)
{
siz[x] = 1;
int now = 0;
for(int i = head[x];i;i = e[i].next)
{
int to = e[i].v;
if(to == last || vis[to]) continue;
dfs(to,x);
siz[x] += siz[to];
now = max(now,siz[to]);
}
now = max(now,sum - siz[x]);
if(now < Minsiz) Minsiz = now,root = x;
}
注意到一个细节：函数里面的“整棵树大小”用了一个\(sum\)变量，是因为每一次在子树中递归时总大小不一样，因为这次是确定了以x为根，下一次进入到儿子\(son\)中，就可以直接用\(siz_{son}\)作为\(sum\)。由于以\(son\)为根dfs时只会改变\(son\)子树的\(siz\)，所以对于\(x\)的其他子树没有影响。
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5,T = 1e7 + 5;
struct Edge{
int v,w,next;
}e[N * 5];
int head[N],n,m,vis[N],dis[N],query[N],judge[N * 100],rt[N],siz[N],rem[N],root = 0,Minsiz = 0x3f3f3f3f,tot = 0,sum,q[N],top = 0;
inline void add(int x,int y,int z)
{
++tot;
e[tot].v = y;
e[tot].w = z;
e[tot].next = head[x];
head[x] = tot;
}
inline void dfs(int x,int last)
{
siz[x] = 1;
int now = 0;
for(int i = head[x];i;i = e[i].next)
{
int to = e[i].v;
if(to == last || vis[to]) continue;
dfs(to,x);
siz[x] += siz[to];
now = max(now,siz[to]);
}
now = max(now,sum - siz[x]);
if(now < Minsiz) Minsiz = now,root = x;
}
inline void getdis(int x,int last)
{
rem[++rem[0]] = dis[x];
for(int i = head[x];i;i = e[i].next)
{
int to = e[i].v;
if(to == last || vis[to]) continue;
dis[to] = dis[x] + e[i].w;
getdis(to,x);
}
}
inline void calc(int x)
{
top = 0;
for(int i = head[x];i;i = e[i].next)
{
int to = e[i].v;
if(vis[to]) continue;
dis[to] = e[i].w;
rem[0] = 0;
getdis(to,x);
for(int j = 1;j <= rem[0];j++)
for(int k = 1;k <= m;k++)
if(query[k] - rem[j] >= 0)
if(judge[query[k] - rem[j]] == 1)
rt[k] = 1;
for(int j = 1;j <= rem[0];j++)
if(rem[j] <= T)
q[++top] = rem[j],judge[rem[j]] = 1;
}
for(int i = 1;i <= top;i++) judge[q[i]] = 0;
}
inline void solve(int x)
{
judge[0] = 1;
vis[x] = 1;
calc(x);
for(int i = head[x];i;i = e[i].next)
{
int to = e[i].v;
if(vis[to]) continue;
sum = siz[to];
Minsiz = 0x3f3f3f3f;
dfs(to,0);
solve(root);
}
}
int main()
{
memset(siz,0,sizeof(siz));
int x,y,z;
cin>>n>>m;
for(int i = 1;i <= n - 1;i++)
{
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
for(int i = 1;i <= m;i++) cin>>query[i];
sum = n;
dfs(1,0);
memset(judge,0,sizeof(judge));
memset(rt,0,sizeof(rt));
memset(vis,0,sizeof(vis));
solve(root);
for(int i = 1;i <= m;i++)
if(rt[i])
cout<<"AYE"<<endl;
else
cout<<"NAY"<<endl;
return 0;
}