题目略了吧，就是一棵树上有多少个点对之间的距离 \(\leq k\)\(n \leq 40000\)
首先有一个 \(O(n^2)\) 的做法，枚举每一个点为起点，\(dfs\) 一遍可知其它点到这个点的距离，统计一下即可。
但是这样太慢了。于是考虑“分治”这种神奇的做法。
第一步，选一个点做根节点，这个点便是树的重心(代码中找重心 \(getroot\) )，它满足每棵子树节点数不超过 \(n/2\) ，即可保证子问题规模减半。
第二步，寻找所有经过根节点的路径，这些路径可以写成 \(u \leadsto rt + v \leadsto rt\) 但是这样有一个问题，\(u\) 和 \(v\) 的 \(lca\) 可能不是 \(rt\) ，即 \(u \leadsto v\) 不经过 \(rt\) 于是我们用容斥原理，枚举 \(rt\) 的每一个儿子把这种情况减去(代码 \(work\) 中的 $ ans-=cal(v,p \to len)$)
顺便提一句如何计算有多少小于 \(k\) 的路径，两个指针扫来扫去就行了(代码中的 \(cal\) ) 复杂度 \(O(n)\)
第三步，对于 \(rt\) 的每一棵子树进行递归（第一步）。
个人认为算法的重点有两个：
\(cal\) 复杂度可为 \(O(n)\) 2.重心可使每棵子树规模减半 这样就使得整个算法复杂度为 \(O(nlogn)\)终于会点分治了，很开心啊~
#include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int N = 40005; struct node{ node *next; int v,len; }pool[N*2],*h[N]; int cnt; void addedge(int u,int v,int len){ node *p=&pool[++cnt],*q=&pool[++cnt]; p->v=v;p->next=h[u];h[u]=p;p->len=len; q->v=u;q->next=h[v];h[v]=q;q->len=len; } int sum,rt,n,k; int size[N],mx[N],vis[N]; void getroot(int u,int f){ int v; size[u]=1; mx[u]=0; for(node *p=h[u];p;p=p->next){ if(vis[v=p->v] || v==f) continue; getroot(v,u); size[u]+=size[v]; mx[u]=max(mx[u],size[v]); } mx[u]=max(mx[u],sum-size[u]); if(mx[u]<mx[rt]) rt=u; } int dep[N],dd; void getdeep(int u,int f,int c){ int v; dep[++dd]=c; size[u]=1; for(node *p=h[u];p;p=p->next){ if(vis[v=p->v] || v==f) continue; getdeep(v,u,c+p->len); size[u]+=size[v]; } } int cal(int u,int c){ int t=0; dd=0; getdeep(u,0,c); sort(dep+1,dep+1+dd); for(int l=1,r=dd;l<r;l++){ while(l<r && dep[l]+dep[r]>k) r--; t+=r-l; } return t; } int ans; void work(int u){ int v; vis[u]=1; ans+=cal(u,0); for(node *p=h[u];p;p=p->next){ if(vis[v=p->v]) continue; ans-=cal(v,p->len); rt=0; sum=size[v]; getroot(v,u); work(rt); } } int main() { int u,v,l; scanf("%d",&n); for(int i=1;i<n;i++){ scanf("%d%d%d",&u,&v,&l); addedge(u,v,l); } scanf("%d",&k); mx[0]=400005; rt=0; sum=n; getroot(1,0); work(rt); printf("%d\n",ans); return 0; }转载于:https://www.cnblogs.com/lindalee/p/9065001.html
