点分治我感觉是图论树部分比较考验脑力的一种题目了
POJ1741
题意：给一棵边带权树，问两点之间的距离小于等于K的点对有多少个
满足条件的点对有两种情况：两个点的路径横跨树根，两个点位于同一颗子树中
对于根节点进行一次dfs，求出deep，并将其从小到大排序
void getdeep(int x,int fa){ dep[++dep[0]]=d[x]; for(int tmp=g[x];tmp;tmp=e[tmp].next) { if(e[tmp].t==fa||vis[e[tmp].t]) continue; d[e[tmp].t]=d[x]+e[tmp].v; getdeep(e[tmp].t,x); }} 然后看一下calculate
int cal(int x,int tmp){ d[x]=tmp;dep[0]=0; getdeep(x,0); sort(dep+1,dep+dep[0]+1); int t=0,l,r; for(l=1,r=dep[0];l 如果我们已经知道了此时所有点到根的距离a[i]
a[x] + a[y] <= k的(x, y)对数就是结果，这个可以通过排序之后O(n)的复杂度求出
然后根据分治的思想，分别对所有的儿子求一遍即可
void work(int x) //点分治 { ans+=cal(x,0); vis[x]=1; for(int tmp=g[x];tmp;tmp=e[tmp].next) { if(vis[e[tmp].t]) continue; ans-=cal(e[tmp].t,e[tmp].v); sum=ch[e[tmp].t]; root=0; getroot(e[tmp].t,root); work(root); }} 但是这会出现重复的——当前情况下两个点位于一颗子树中，那么应该将其减掉
显然这两个点是满足题意的，为什么减掉呢？因为在对子树进行求解的时候，会重新计算
在进行分治时，为了避免树退化成一条链而导致时间复杂度变为O(N^2)，每次都找树的重心
这样，所有的子树规模就会变的很小了。时间复杂度O(Nlog^2N)
void getroot(int x,int fa){ ch[x]=1;f[x]=0; for(int tmp=g[x];tmp;tmp=e[tmp].next) { if(e[tmp].t==fa||vis[e[tmp].t]) continue; getroot(e[tmp].t,x); ch[x]+=ch[e[tmp].t]; f[x]=max(f[x],ch[e[tmp].t]); } f[x]=max(f[x],sum-ch[x]); if(f[x] 有了板子不能救命，还要大量刷大量刷才可以，点分治确实是一个要命的地方，上次的省赛的一道题就栽了
1 #include2 #include 3 #include 4 using namespace std; 5 const int maxn=10005; 6 const int maxm=20005; 7 const int INF=0x7fffffff; 8 int n,k,ans; 9 int cnt,g[maxn]; 10 struct Edge{ int t,next,v;}e[maxm]; 11 12 int root,sum; 13 int ch[maxn],f[maxn],dep[maxn],d[maxn]; 14 bool vis[maxn]; 15 16 void addedge(int u,int v,int w) 17 { 18 cnt++; 19 e[cnt].t=v;e[cnt].v=w; 20 e[cnt].next=g[u];g[u]=cnt; 21 } 22 int read() 23 { 24 int x=0,f=1;char ch=getchar(); 25 while(ch<'0'||ch>'9') { if(ch=='0')f=-1;ch=getchar();} 26 while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();} 27 return x*f; 28 } 29 void getroot(int x,int fa) 30 { 31 ch[x]=1;f[x]=0; 32 for(int tmp=g[x];tmp;tmp=e[tmp].next) 33 { 34 if(e[tmp].t==fa||vis[e[tmp].t]) continue; 35 getroot(e[tmp].t,x); 36 ch[x]+=ch[e[tmp].t]; 37 f[x]=max(f[x],ch[e[tmp].t]); 38 } 39 f[x]=max(f[x],sum-ch[x]); 40 if(f[x]