点分治

点分治是一种在树上进行的分治，可以方便的求解树上路径等问题。

例题：P3806 【模板】点分治 1

给定一棵树，询问树上是否存在长度为k的路径。
现在我们假设x为根节点，
那么一条路径长度为k有两种情况，
一种是经过x，一种不经过x，
第一种的两个端点在两个不同子树中，
第二种的两个端点在同一子树中，
那么我们选择求解第一种，
第二种也就变成了子问题分治解决。

为了使第一种的求解尽量的快速，我们需要对一颗树以它的重心为根，
这样就可以把复杂度均摊，
假如计算的复杂度为\(O(n)\)(n为树点数)，
那么总共的复杂度为\(O(nlog^2n)\).

框架如下：

#include<algorithm>
#include<stdio.h>
#define maxn 100005
using namespace std;
int n;
int head[maxn],to[maxn<<1],nex[maxn<<1],len[maxn<<1],m1;
void add(int u,int v,int w) {
	to[++m1]=v,nex[m1]=head[u],len[m1]=w,head[u]=m1;
}
int vis[maxn],son[maxn];
int root,minn=1e9;
void getroot(int now,int last,int siz) {
	int num=0; son[now]=1;
	for(int i=head[now];i;i=nex[i]) {
		int st=to[i]; if(st==last || vis[st]) continue;
		getroot(st,now,siz);
		num=max(num,son[st]);
		son[now]+=son[st];
	}	
	num=max(num,siz-son[now]);
	if(num<minn) minn=num,root=now;
}
void calc(int now) {
	
}
void solve(int now) {
	vis[now]=1;
	calc(now);
	for(int i=head[now];i;i=nex[i]) {
		int st=to[i]; if(vis[st]) continue;
		minn=1e9; getroot(st,now,son[st]);
		solve(root);
	}
}
int main() {
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
	scanf("%d",&n);
	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);
	}
	getroot(1,0,n);
	solve(root);
	return 0;
}