点分治：
点分治的题目基本一样，都是路径计数。
其复杂度的保证是依靠 $O(n)$ 找重心的，每一次至少将问题规模减小为原先的$1/2$。
找重心我喜欢$BFS$防止爆栈。
int Root(int x){
dfsn[]=;
q.push(x); fa[x]=;
flag[x]=;
while(!q.empty()){
int x=q.front(); q.pop();
dfsn[++dfsn[]]=x;
for(int i=g[x];i;i=E[i].to)
if(!v[p] && !flag[p]){
fa[p]=x;
flag[p]=;
q.push(p);
}
}
for(int i=;i<=dfsn[];i++){
siz[dfsn[i]]=;
h[dfsn[i]]=;
flag[dfsn[i]]=;
}
int root=;
for(int i=dfsn[];i>=;i--){
int x=dfsn[i];
if(fa[x]){
siz[fa[x]]+=siz[x];
h[fa[x]]=max(h[fa[x]],siz[x]);
}
h[x]=max(h[x],dfsn[]-siz[x]);
if(!root || h[x]<h[root]) root=x;
}
return root;
}
故总共有 $O(logn)$ 层。
在每一层我们分别对不同的块（删点而形成）采用 $O(siz[p])$ 的算法。
主定理 $T(n) = T(n/2) + O(n)$
总体上是 $O(nlogn)$
大体框架如下
void DC(int x){
v[x]=;
for(int i=g[x];i;i=E[i].to)
if(!v[p]){
// 大体上是f[x]*ft[x]就是
// Ans = (之前的子树的路径数)*（当前子树的路径数）
}
// 将标记什么的清空，注意保证复杂度是O(siz)不是O(n)
for(int i=g[x];i;i=E[i].to)
if(!v[p]) DC(Root(p));
}
然后对于点分治路径的统计，通常有dp，数据结构，数论等等的方法。
注意：要记得上面的方法没有统计以点x为起点的路径条数，记得加上。
例题：
BZOJ 3697
题意：
给出一棵树，每一条边为黑或白，统计满足条件的路径数
1.路径上黑色和白色的个数相等
2.路径上存在一个点使得起点到当前点黑色和白色的个数相等，此点不能是起点终点。
乍一看是没有解法的，套用点分治。
问题转化为统计过点x的合法路径条数。
套用dp
$f(x,0)$ 表示和为x，无休息站的
$f(x,1)$ 表示和为x，有休息站的
$$ans = f(0,0) * ft(0,0) + \sum_{i=-d}^d {f(i,0) \cdot ft(-i,1) + f(i,1) \cdot ft(-i,0) + f(i,1) \cdot ft(-i,1)} $$
条件2可以转化为在当前点到x的路径上有点的$dis(p) = dis(now)$
所以注意保证初始化的复杂度
所以记录一下当前的最大深度，初始化 $f$ 数组和 $ft$ 数组的时候从0循环到 $max deep$
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue> #define N 400010
#define p E[i].x
#define LL long long
#define debug(x) cout<<#x<<" = "<<x<<endl; /*
树形dp
f(x,0) 表示和为x，无休息站的
f(x,1) 表示和为x，有休息站的
ans = f[0][0] * ft[0][0] +
∑ f[i][0]*ft[-i][1] + f[i][1]*ft[-i][0] + f[i][1]*ft[-i][1]
(-d <= i <= d)
*/ using namespace std; struct edge{
int x,to,v;
}E[N<<]; int n,totE;
int g[N],dfsn[N],fa[N],siz[N],h[N];
bool v[N],flag[N];
LL ans;
LL f[N][],ft[N][];
queue<int> q; void ade(int x,int y,int v){
E[++totE]=(edge){y,g[x],v}; g[x]=totE;
} int Root(int x){
dfsn[]=;
q.push(x); fa[x]=;
flag[x]=;
while(!q.empty()){
int x=q.front(); q.pop();
dfsn[++dfsn[]]=x;
for(int i=g[x];i;i=E[i].to)
if(!v[p] && !flag[p]){
fa[p]=x;
flag[p]=;
q.push(p);
}
}
for(int i=;i<=dfsn[];i++){
siz[dfsn[i]]=;
h[dfsn[i]]=;
flag[dfsn[i]]=;
}
int root=;
for(int i=dfsn[];i>=;i--){
int x=dfsn[i];
if(fa[x]){
siz[fa[x]]+=siz[x];
h[fa[x]]=max(h[fa[x]],siz[x]);
}
h[x]=max(h[x],dfsn[]-siz[x]);
if(!root || h[x]<h[root]) root=x;
}
return root;
} int mxdep;
int cnt[N],d[N],dis[N]; void dfs(int x,int fa){
mxdep=max(mxdep,d[x]);
if(cnt[dis[x]]) ft[dis[x]][]++;
else ft[dis[x]][]++;
cnt[dis[x]]++;
for(int i=g[x];i;i=E[i].to)
if(p!=fa&&!v[p]){
d[p]=d[x]+;
dis[p]=dis[x]+E[i].v;
dfs(p,x);
}
cnt[dis[x]]--;
} void DC(int x){
v[x]=;
f[n][]=;
int mx=;
for(int i=g[x];i;i=E[i].to)
if(!v[p]){
dis[p]=n+E[i].v;
d[p]=mxdep=;
dfs(p,p);
mx=max(mx,mxdep);
ans+=(f[n][]-)*ft[n][];
for(int j=-mxdep;j<=mxdep;j++){
ans+=ft[n-j][]*f[n+j][]+
ft[n-j][]*f[n+j][]+ft[n-j][]*f[n+j][];
}
for(int j=n-mxdep;j<=n+mxdep;j++){
f[j][]+=ft[j][];
f[j][]+=ft[j][];
ft[j][]=ft[j][]=;
}
}
for(int i=n-mx;i<=n+mx;i++)
f[i][]=f[i][]=;
for(int i=g[x];i;i=E[i].to)
if(!v[p]) DC(Root(p));
} int main(){
scanf("%d",&n);
for(int i=,x,y;i<n;i++){
int v;
scanf("%d%d%d",&x,&y,&v);
if(!v) v=-;
ade(x,y,v); ade(y,x,v);
}
DC(Root());
printf("%lld\n",ans);
return ;
}
然后是HDU 4812
题意：给出一棵树，每一个点有一个点权，找到一条点权乘积为K的路径，输出起点和终点，要求字典序最小。
求一下逆元，然后用map记录前面的所有子树能够到达的权值（乘积）
注意这是点权，不同于边权，所以在处理过点x的路径的时候要谨慎，我的做法是将路径拆为 x点 ， 之前子树中的一条链， 当前子树中的一条链。
用map复杂度多一个log，然而也能过。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue> #define N 400010
#define LL long long
#define mod 1000003
#define p E[i].x
#define INF 0x3f3f3f3f
#define ipos map<int,int>::iterator using namespace std; struct edge{
int x,to;
}E[N<<]; map<int,int> ft,f;
int n,ansv[],totE,K;
int h[N],g[N],siz[N],a[N],fa[N],dfsn[N],dis[N];
bool v[N],flag[N];
queue<int> q; int add(int a,int b){
if(a+b>=mod) return a+b-mod;
return a+b;
} int mul(int a,int b){
return (int)((LL)a*(LL)b%mod);
} int qpow(int x,int n){
int ans=;
for(;n;n>>=,x=mul(x,x))
if(n&) ans=mul(ans,x);
return ans;
} int inv(int x){
return (int)qpow((LL)x,mod-2LL);
} void ade(int x,int y){
E[++totE]=(edge){y,g[x]}; g[x]=totE;
} int Root(int x){
dfsn[]=;
q.push(x); fa[x]=;
flag[x]=;
while(!q.empty()){
int x=q.front(); q.pop();
dfsn[++dfsn[]]=x;
for(int i=g[x];i;i=E[i].to)
if(!v[p] && !flag[p]){
fa[p]=x;
flag[p]=;
q.push(p);
}
}
for(int i=;i<=dfsn[];i++){
siz[dfsn[i]]=;
h[dfsn[i]]=;
flag[dfsn[i]]=;
}
int root=;
for(int i=dfsn[];i>=;i--){
int x=dfsn[i];
if(fa[x]){
siz[fa[x]]+=siz[x];
h[fa[x]]=max(h[fa[x]],siz[x]);
}
h[x]=max(h[x],dfsn[]-siz[x]);
if(!root || h[x]<h[root]) root=x;
}
return root;
} void bfs(int x){
dfsn[]=;
q.push(x); flag[x]=;
while(!q.empty()){
int x=q.front(); q.pop();
dfsn[++dfsn[]]=x;
if(!ft.count(dis[x]) || ft[dis[x]]>x)
ft[dis[x]]=x;
for(int i=g[x];i;i=E[i].to)
if(!v[p] && !flag[p]){
flag[p]=;
dis[p]=mul(dis[x],a[p]);
q.push(p);
}
}
for(int i=;i<=dfsn[];i++)
flag[dfsn[i]]=;
} void upd(int a,int b){
if(a>b) swap(a,b);
if(ansv[]>a || ansv[]==a&&ansv[]>b){
ansv[]=a;
ansv[]=b;
}
} void DC(int x){
// printf("node : %d\n",x);
v[x]=;
f.clear();
f[]=x;
for(int i=g[x];i;i=E[i].to)
if(!v[p]){
ft.clear();
dis[p]=a[p];
bfs(p);
for(ipos it=ft.begin();it!=ft.end();it++){
int tmp=(*it).first;
if(f.count(mul(mul(K,inv(tmp)),inv(a[x])))){
upd(f[mul(mul(K,inv(tmp)),inv(a[x]))],
(*it).second);
}
}
for(ipos it=ft.begin();it!=ft.end();it++){
if(!f.count((*it).first)) f[(*it).first]=(*it).second;
else f[(*it).first]=min(f[(*it).first],(*it).second);
}
}
for(int i=g[x];i;i=E[i].to)
if(!v[p]) DC(Root(p));
} int main(){
// freopen("test.in","r",stdin);
while(scanf("%d%d",&n,&K)==){
ansv[]=ansv[]=INF;
totE=;
for(int i=;i<=n;i++) g[i]=;
for(int i=;i<=n;i++) scanf("%d",&a[i]),v[i]=;
for(int i=,x,y;i<n;i++){
int v;
scanf("%d%d",&x,&y);
ade(x,y);
ade(y,x);
}
DC(Root());
if(ansv[]==INF) puts("No solution");
else printf("%d %d\n",ansv[],ansv[]);
}
return ;
}
最后是 国家集训队的 crash的文明世界
题意：
定义：
求所有点的S(i)
很显然是点分治，斯特林数是什么，我不会 TAT
记录$f(i)$表示$\sum {dist(p,x)^i }$，$ft$同理
考虑每一次统计过x的路径时将过x的路径的影响加入子树中的点，同时在最后将$S(i)$加上$f(K)$
坑点就是合并的时候要用一下 二项式展开
$$ S(p) += \sum_{i=0}^K {C(K,i) * f(K-i) * b^i}$$
然后注意要统计全路径，所以上面的框架不适用（上面的框架对于当前子树只能统计遍历过的子树，而应该是统计所有除了当前子树的权值和）
然后就可以了，自己歪歪（看不懂题解），一遍AC爽。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue> #define N 200010
#define mod 10007
#define M 310
#define p E[i].x using namespace std;
/*
f[j] 之前的 dist(x,p)^j
ft[j] 当前的 dist(x,p)^j
S[p] += ∑C(K,i) * a^{K-i} * b^i (0<=i<=K)
O(lognK)
*/ int n,K,totE;
int g[N],f[M],siz[N],h[N],fa[N],dfsn[N],S[N],d[N];
int C[M][M];
bool v[N],flag[N];
queue<int> q; int add(int a,int b){
if(a+b>=mod) return a+b-mod;
return a+b;
} int mul(int a,int b){
return a*b%mod;
} struct edge{
int x,to;
}E[N<<]; void ade(int x,int y){
E[++totE]=(edge){y,g[x]}; g[x]=totE;
} int qpow(int x,int n){
int ans=;
for(;n;n>>=,x=mul(x,x))
if(n&) ans=mul(ans,x);
return ans;
} int Root(int x){
dfsn[]=;
q.push(x); fa[x]=;
flag[x]=;
while(!q.empty()){
int x=q.front(); q.pop();
dfsn[++dfsn[]]=x;
for(int i=g[x];i;i=E[i].to)
if(!v[p] && !flag[p]){
fa[p]=x;
flag[p]=;
q.push(p);
}
}
for(int i=;i<=dfsn[];i++){
siz[dfsn[i]]=;
h[dfsn[i]]=;
flag[dfsn[i]]=;
}
int root=;
for(int i=dfsn[];i>=;i--){
int x=dfsn[i];
if(fa[x]){
siz[fa[x]]+=siz[x];
h[fa[x]]=max(h[fa[x]],siz[x]);
}
h[x]=max(h[x],dfsn[]-siz[x]);
if(!root || h[x]<h[root]) root=x;
}
return root;
} void bfs(int x){
dfsn[]=; d[x]=;
q.push(x); flag[x]=;
while(!q.empty()){
int x=q.front(); q.pop();
dfsn[++dfsn[]]=x;
for(int i=g[x];i;i=E[i].to)
if(!v[p] && !flag[p]){
d[p]=d[x]+;
flag[p]=;
q.push(p);
}
}
for(int i=;i<=dfsn[];i++){
int tmp=;
for(int j=;j<=K;j++){
f[j]=add(f[j],tmp);
tmp=mul(tmp,d[dfsn[i]]);
}
flag[dfsn[i]]=;
}
} int power[M]; void solve(int rt){
dfsn[]=; d[rt]=;
q.push(rt); flag[rt]=;
while(!q.empty()){
int x=q.front(); q.pop();
dfsn[++dfsn[]]=x;
for(int i=g[x];i;i=E[i].to)
if(!v[p] && !flag[p]){
d[p]=d[x]+;
flag[p]=;
q.push(p);
}
}
for(int i=;i<=dfsn[];i++){
int tmp=;
for(int j=;j<=K;j++){
f[j]=(f[j]-tmp+mod)%mod;
tmp=mul(tmp,d[dfsn[i]]);
}
}
// printf("son : %d\n",rt);
// for(int i=0;i<=K;i++){
// printf("%d%c",f[i],i==K?'\n':' ');
// }
for(int t=;t<=dfsn[];t++){
int x=dfsn[t];
flag[x]=;
power[]=;
for(int i=;i<=K;i++) power[i]=mul(power[i-],d[x]);
for(int i=;i<=K;i++){
// printf("addto %d = %d\n",x,mul(C[K][i], mul(f[K-i],power[i])));
S[x] = add(S[x], mul(C[K][i], mul(f[K-i],power[i])));
}
S[x]=add(S[x],power[K]);
}
// S[x]=add(S[x],power[K]);
for(int i=;i<=dfsn[];i++){
int tmp=;
for(int j=;j<=K;j++){
f[j]=add(f[j],tmp);
tmp=mul(tmp,d[dfsn[i]]);
}
}
}
//S[p] += ∑C(K,i) * a^{K-i} * b^i (0<=i<=K)
void DC(int x){
v[x]=;
// printf("node : %d\n",x);
// for(int i=1;i<=dfsn[0];i++)
// printf("%d%c",dfsn[i],i==dfsn[0]?'\n':' ');
for(int i=;i<=K;i++) f[i]=;
for(int i=g[x];i;i=E[i].to)
if(!v[p]) bfs(p);
// printf("before\n");
// for(int i=0;i<=K;i++) printf("%d%c",f[i],i==K?'\n':' ');
for(int i=g[x];i;i=E[i].to)
if(!v[p]) solve(p);
S[x]=add(S[x],f[K]);
// printf("base = %d\n",f[K]);
for(int i=g[x];i;i=E[i].to)
if(!v[p]) DC(Root(p));
} int main(){
freopen("civilization.in","r",stdin);
freopen("civilization.out","w",stdout);
scanf("%d%d",&n,&K);
C[][]=;
for(int i=;i<=K;i++){
C[i][]=;
for(int j=;j<=i;j++)
C[i][j]=add(C[i-][j-],C[i-][j]);
}
int L,now,A,B,Q,tmp;
scanf("%d%d%d%d%d",&L,&now,&A,&B,&Q);
for(int i=,x,y;i<n;i++){
now=(now*A+B)%Q;
tmp=(i<L)? i:L;
x=i-now%tmp;
y=i+;
ade(x,y);
ade(y,x);
}
DC(Root());
for(int i=;i<=n;i++){
printf("%d\n",S[i]);
}
return ;
}
总结完了点分治，NOI必胜。