學習了一下點分治，如果理解有誤還請不吝賜教。

為了快速求得樹上任意兩點之間距離滿足某種關系的點對數(shù)，我們需要用到這種算法。

點分治是樹上的一種分治算法，依靠樹和子樹之間的關系進行分治從而降低復雜度。

和其他樹上的算法有一些區(qū)別的是，點分治算法不是先處理局部信息，再將他們匯總得到整個樹的信息。點分治處理的問題一般不是樹整體的信息，而是樹上局部的關系，這就導致我們不能將它看作一個整體，而應該從一開始就處理，在從上往下處理的過程中不斷完善信息。在這種思想下我覺得能夠更好的理解這個算法。

例如：

Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.
Input
The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l.
The last test case is followed by two zeros.
Output
For each test case output the answer on a single line.
Sample Input
5 4
1 2 3
1 3 1
1 4 2
3 5 1
0 0
Sample Output
8

題目的大概意思就是說，想要找到樹上兩點之間距離小于k的點對數(shù)（路徑是有長度的）。我們如何使用點分治算法來解決這個問題呢？

為了找到合適的分治方法，我們引入一個概念叫做樹的重心。樹的重心指的是以該節(jié)點為根形成的最大子樹規(guī)模最小的節(jié)點。聽起來可能有點繞，其實還是挺符合直覺的。指的就是，一個樹有多個節(jié)點，每個節(jié)點都可以作為這個樹的根，而一旦根節(jié)點確定，就會有多個子樹，這些子樹中規(guī)模最大的一般是根節(jié)點下直接相連的某個子樹。所謂樹的重心，就是這個最大子樹規(guī)模最小的節(jié)點。比如：
在上面這個圖中，我們選擇i節(jié)點作為樹的重心，它的子樹中規(guī)模最大的是3，選擇其他的都會比3大。

知道什么是重心以后，我們來看如何求一個樹的重心。直接看代碼吧

void GetRoot(int x,int father) {int v;SonNum[x]=1;//子樹節(jié)點的總個數(shù)MaxNum[x]=1;//最大子樹的節(jié)點個數(shù)for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; //Vis[v]是用來標記是否已經處理過該節(jié)點了，這個標記會在后面修改，如果已經處理過我們就不要將這個節(jié)點再考慮進來了if(v==father || Vis[v]) continue;GetRoot(v,x);SonNum[x]+=SonNum[v];if(SonNum[v]>MaxNum[x]) MaxNum[x]=SonNum[x];}MaxNum[x]=max(MaxNum[x],ss-SonNum[x]);if(rootx>MaxNum[x]) root=x,rootx=MaxNum[x]; }

得到樹的重心以后我們就要對他進行處理，首先當然是統(tǒng)計子樹上任意一點到樹根（也就是樹的重心）的距離

void GetDis(int x,int father,int dis) {int v;//Dis數(shù)組記錄樹上其他點到重心的距離，因為我們不需要知道哪個點，所以直接保存就可以Dis[++dlen]=dis;for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(v==father|| Vis[v]) continue;GetDis(v,x,dis+Edge[i].len);} }

得到距離以后我們就可以根據(jù)題目的要求進行計數(shù)啦。這里要求的是任意兩點的距離小于k，那我們就要先得到兩點間的距離。在以重心為根的樹上，在兩個不同子樹上的點的距離就是他們距離重心的距離和。可是如果在同一個子樹上的話就不是這樣了。但是我們不好確定兩個節(jié)點是否在同一個子樹上，所以先囫圇吞棗將同一個子樹上的都計算上，然后再訪問子樹將他們減去。

int Count(int x,int dis) {for(int i=0;i<=dlen;++i) Dis[i]=0;dlen=0;GetDis(x,0,dis);sort(Dis+1,Dis+1+dlen);int l=1,r=dlen,ret=0;//如果l到r的距離小于k，則l到l和r之間的任意一點的距離都小于k，所以直接加上r-lwhile(l<=r){if(Dis[l]+Dis[r]<=kk) ret+=r-l,l++;else r--;}return ret; }

但是顯然這樣是多算的，我們要減去在同一個子樹上的滿足條件的節(jié)點，他們會在更后面再次加上。

void Solve(int x) {int v;ans+=Count(x,0);Vis[x]=true;for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(Vis[v]) continue;//在這里減去同一個子樹的上錯誤加上的點ans-=Count(v,Edge[i].len);ss=SonNum[v]; rootx=INT_MAX; root=0;//處理子樹，再加上正確的點GetRoot(v,x);Solve(root);} }

可能稍微有些難以理解的是為什么這樣就可以減去剛開始錯誤地加上的同一個子樹上的點。這里稍微解釋一下：

還是以這個圖為例，假如我們一開始處理的是樹的重心i節(jié)點，那么我們正確計算的就是分布在四個子樹上之間的距離，錯誤計算的就是同一個子樹之間的距離，例如：D-A-i-A-E和E-A-i-A等，為了處理這個問題，我們后面又訪問了一下子節(jié)點，注意上面的Solve函數(shù)中的ans-=Count(v,Edge[i].len);，為什么這樣寫就可以減去子節(jié)點的影響呢？需要注意我們已經將重心的Vis[x]的值已經修改，因此子節(jié)點無法訪問除了當前子樹外的其他子樹，而且有一個初值Edge[i].len，這樣處理以后他們的Dis數(shù)組的值和之前從重心訪問是相同的。也就是說，之前會計入答案的，這里也會再次記入答案，且只計入了同一個子樹中的。減去他們以后就是正確的數(shù)目。

然后我們再訪問子樹。將子樹看作一個單獨的樹，再次同樣的處理。

AC代碼：

#include<iostream> #include<cstring> #include<cstdio> #include<climits> #include<algorithm> #include<ctime> #include<cstdlib> #include<queue> #include<set> #include<map> #include<cmath>using namespace std;const int MAXN=1e5+5; struct edge {int to,len,last; }Edge[MAXN<<1]; int Last[MAXN],tot; int n,kk,SonNum[MAXN],MaxNum[MAXN],Vis[MAXN],Dis[MAXN]; int ans,root,rootx,dlen,ss;int getint() {int x=0,sign=1; char c=getchar();while(c<'0' || c>'9'){if(c=='-') sign=-1; c=getchar();}while(c>='0' && c<='9'){x=x*10+c-'0'; c=getchar();}return x*sign; }void Init() {for(int i=0;i<=n;++i) Last[i]=0; tot=0; ans=0; for(int i=0;i<=n;++i) Vis[i]=false; }void AddEdge(int u,int v,int w) {Edge[++tot].to=v; Edge[tot].len=w; Edge[tot].last=Last[u]; Last[u]=tot; }void Read() {int u,v,w;for(int i=1;i<n;i++){u=getint(); v=getint(); w=getint();AddEdge(u,v,w); AddEdge(v,u,w);} }void GetRoot(int x,int father) {int v;SonNum[x]=1; MaxNum[x]=1;for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(v==father || Vis[v]) continue;GetRoot(v,x);SonNum[x]+=SonNum[v];if(SonNum[v]>MaxNum[x]) MaxNum[x]=SonNum[x];}MaxNum[x]=max(MaxNum[x],ss-SonNum[x]);if(rootx>MaxNum[x]) root=x,rootx=MaxNum[x]; }void GetDis(int x,int father,int dis) {int v;Dis[++dlen]=dis;for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(v==father|| Vis[v]) continue;GetDis(v,x,dis+Edge[i].len);} }int Count(int x,int dis) {for(int i=0;i<=dlen;++i) Dis[i]=0;dlen=0;GetDis(x,0,dis);sort(Dis+1,Dis+1+dlen);int l=1,r=dlen,ret=0;while(l<=r){if(Dis[l]+Dis[r]<=kk) ret+=r-l,l++;else r--;}return ret; }void Solve(int x) {int v;ans+=Count(x,0);Vis[x]=true;for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(Vis[v]) continue;ans-=Count(v,Edge[i].len);ss=SonNum[v]; rootx=INT_MAX; root=0;GetRoot(v,x);Solve(root);} }void Work() {rootx=INT_MAX; ss=n; root=0;GetRoot(1,0); Solve(root); }void Write() {printf("%d\n",ans); }int main() {while(1){Init();n=getint(); kk=getint();if(n==0 && kk==0) break;Read();Work();Write();}return 0; }

參考博客：傳送門

總結

以上是生活随笔為你收集整理的POJ 1741tree-点分治入门的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。