首先给出定义
点分治是一种处理树上路径的工具
挂出一道题目来：Master of Subgraph
这道题目让你求所有联通子图加和所能产生数字，问你1到m之间，那些数字可以被产生
这道题目，假如我们利用暴力的方法去求解的话
实际上是对每个节点进行一次dfs，这样的话会发现复杂度为O（N^2）也就是再9e6左右，再加上常数M/64，复杂度根本不够(9e9)
我们可以利用点分治去优化复杂度
点分治的原理就是树上的路径产生的答案，不是在经过这个节点的就是在不经过这个节点的，那我们找到树的重心的话，就能够算出来经过该点的所有答案，然后依次递归大约logN层，这样复杂度就变成了NlogN的程度，也就是3e4*1e3=3e7加上常数，再加上时间的宽限，完全够用
所以点分治就是树上分治的一种，减小重复计算的东西，不断逐步缩小子树的计算
其中一般来说要开 一个父节点数组，一个儿子数数组，来计算重心的位置
然后就是点分治，跟递归差不多就是要去计算答案
然后就是利用solve函数，每次点分治计算树根，然后依次处理子树的重心节点然后继续递归继续分治
#include <iostream>
#include <cstring>
#include <vector>
#include <bitset>
;
;
int E[MAXN][MAXN];
int all[MAXN];
int f[MAXN],son[MAXN],root,tot;
/*
分别代表f[x]的两侧孩子数目的最大值，重心的孩子数目最小
son代表以x为根的孩子数目
root是被移动的根
tot是当前根的孩子总数
*/
bool vis[MAXN];
std::bitset<MAXM>b[MAXN],ans;
int n,m,val[MAXN];
void dfs(int x,int fa){
/* dfs搜索树，将根移动到树的重心，降低dp层数 */
f[x] = ;
/* 标记孩子数目为0 */
son[x] = ;
/* 计算孩子数目 */
; i <= all[x]; i++)
{
int y=E[x][i];
if(!vis[y] && y!=fa)
{
dfs(y,x);
/* 递归进入子数 */
f[x] = std::max(f[x],son[y]);
/* 计算子树中孩子数目最多的子树孩子数 */
son[x]+=son[y];
/* 累加孩子数目 */
}
}
f[x]=std::max(f[x],tot-f[x]);
/* 计算该根节点最大孩子数其余侧的数目中两边的最大值 */
if(f[x]<f[root]) root=x;
/* 移动根节点，寻找重心 */
}
void getdp(int x, int fa){
b[x]<<=val[x];
/* 累加val[x] */
son[x]=;
;i<=all[x];i++)
{
int y=E[x][i];
if(!vis[y] && y!=fa)
{
b[y]=b[x];
getdp(y,x);
son[x]+=son[y];
b[x]|=b[y];
}
}
}
void solve(int x){
vis[x] = true;
b[x] = ;
getdp(x,);
/* 以某一点为根进行点分治 */
ans|=b[x];
/* 累加答案 */
;i<=all[x];i++)
{
/* 子树递归进行点分治 */
int y=E[x][i];
if(!vis[y])
{
tot = son[y];
root = ;
dfs(y,x);
/* 先寻找树根 */
solve(root);
/* 递归分治 */
}
}
}
int main(){
int T;
std::cin>>T;
while(T--)
{
scanf("%d%d",&n,&m);
;i<=n;i++) all[i]=;
ans.reset();
memset(vis,,sizeof(vis));
;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
E[x][++all[x]]=y;
E[y][++all[y]]=x;
}
;i<=n;i++)
{
scanf("%d",&val[i]);
}
f[] = n+;
tot=n;
dfs(,root);
solve(root);
;i<=m;i++)
{
printf("%d",(int)ans[i]);
}
puts("");
}
;
}