树上分治 点分治 \(O(nlogn)\)
主要解决有关树上路径统计的问题(其中路径的边权可能需要满足一些条件)
1.基本思想：点分治的本质其实是将一棵树拆分成许多棵子树处理，并不断进行。
2.分治点的选择：树的重心
3.点分治
路径的两个端点在同一个子树内
路径的两个端点不在同一个子树内
路径的某个端点是重心
基本模板
#include <bits/stdc++.h> #define fi first #define se second #define ll long long using namespace std; const int N=1e4+5; vector<pair<int,int>>E[N]; int n,k,S; //S记录根据重心划分之后当前遍历的子树的大小 int sz[N],mxson[N]; bool vis[N];//是否是重心 int MX,root,dist[N],cnt; ll ans; void getroot(int u,int fa) { sz[u]=1,mxson[u]=0; for(auto [v,w]:E[u]) { if(v==fa||vis[v]) continue; getroot(v,u); sz[u]=sz[u]+sz[v]; mxson[u]=max(mxson[u],sz[v]); } mxson[u]=max(mxson[u],S-sz[u]); if(mxson[u]<MX) root=u,MX=mxson[u]; } void getdist(int u,int fa) { } int solve(int u) { } //分治难点在于统计合并答案 void Divide(int u) { solve(u,1); //统计答案 vis[u]=1; for(auto [v,w]:E[u]) { if(vis[v]) continue; solve(v,-1); //统计答案(这里可能会用到容斥之类的) S=sz[v],root=0,MX=N; getroot(v,0); Divide(root); } return; } int main() { ios::sync_with_stdio(false); cin.tie(0); while(cin>>n>>k,n&&k) { for(int i=1;i<=n;i++) vis[i]=0,E[i].clear(); for(int i=1;i<n;i++) { int u,v,w; cin>>u>>v>>w; u++,v++; E[u].push_back({v,w}); E[v].push_back({u,w}); } ans=0; S=n,MX=N; getroot(1,0); Divide(root); cout<<ans<<'\n'; } } 基础例题 1.给定一个有 \(N\)个点（编号 \(0,1,…,N−1\)）的树，每条边都有一个权值（不超过 1000）。
树上两个节点 \(x\) 与 \(y\) 之间的路径长度就是路径上各条边的权值之和。
求长度不超过 \(K\) 的路径有多少条。
思路：分治后在每个子树中暴力求出所有点到分治点的距离，然后将所有距离存在一个数组中排序，利用双指针的方法统计答案，然后对于记重的边用容斥原理去解决。
#include <bits/stdc++.h> #define fi first #define se second #define ll long long using namespace std; const int N=1e4+5; vector<pair<int,int>>E[N]; int n,k,S; //S记录根据重心划分之后当前遍历的子树的大小 int sz[N],mxson[N]; bool vis[N];//是否是重心 int MX,root,dist[N],cnt; ll ans; void getroot(int u,int fa) { sz[u]=1,mxson[u]=0; for(auto [v,w]:E[u]) { if(v==fa||vis[v]) continue; getroot(v,u); sz[u]=sz[u]+sz[v]; mxson[u]=max(mxson[u],sz[v]); } mxson[u]=max(mxson[u],S-sz[u]); if(mxson[u]<MX) root=u,MX=mxson[u]; } void getdist(int u,int fa,int d) { dist[++cnt]=d; for(auto [v,w]:E[u]) { if(v==fa||vis[v]) continue; getdist(v,u,w+d); } return; } int solve(int u,int d) { cnt=0; memset(dist,0,sizeof dist); getdist(u,0,d); sort(dist+1,dist+1+cnt); int l=1,r=cnt,res=0; while(l<=r) //排序后双指针统计答案 { if(dist[r]+dist[l]<=k) res+=r-l,l++; else r--; } return res; } void Divide(int u) { ans=ans+solve(u,0); vis[u]=1; for(auto [v,w]:E[u]) { if(vis[v]) continue; ans=ans-solve(v,w); //容斥原理 S=sz[v],root=0,MX=N; getroot(v,0); Divide(root); } return; } int main() { ios::sync_with_stdio(false); cin.tie(0); while(cin>>n>>k,n&&k) { for(int i=1;i<=n;i++) vis[i]=0,E[i].clear(); for(int i=1;i<n;i++) { int u,v,w; cin>>u>>v>>w; u++,v++; E[u].push_back({v,w}); E[v].push_back({u,w}); } ans=0; S=n,MX=N; getroot(1,0); Divide(root); cout<<ans<<'\n'; } } 2.给定一棵 \(N\)个节点的树，每条边带有一个权值。
求一条简单路径，路径上各条边的权值和等于 \(K\)，且路径包含的边的数量最少。
题意：给定一个\(n\)个节点的数，问树上任选两点间且这两点间的距离为素数的概率是多少