http://poj.org/problem?id=1741

題目大意：給一棵樹，求點對間距離<=k的個數。

————————————————————

以這道題為例記錄一下對于樹分治的理解。

樹分治分為兩類，一類是基于點的分治，一類是基于邊的分治。

后者與樹鏈剖分很相似，但是一般用不上，這里講的是前者。

我們一般進行樹分治找的點都是這棵樹的重心（即子樹最大者最小的點），我們每次操作都做與這個點相關的路徑，然后刪除這個點再重新尋找。

分重心的好處在于我們近似的將樹分成了兩份，類似于二分，其深度不超過O(logn)（其實有嚴格證明的，但是我太弱了，不會寫）

分完重心的操作大致三種

1.找u，v，其中u，v在重心s的同一棵子樹上（這種情況直接忽略，因為看下面的操作我們就能明白我們可以遞歸的完成這個操作）

2.找u，v，其中u，v在重心s的兩棵子樹上。

3.找u，查找u到重心s的路徑。

我們發現3操作和2操作很相似，我們直接討論2操作。

顯然我們在2操作的路徑當中不可避免的要經過s，所以我們從s開始bfs，求出每個點i到s的距離dis[i]，我們的路徑長度即為dis[u]+dis[v]。

3操作同理只是變成了dis[u]+dis[s]，其中dis[s]=0.

這里提供一種簡要算法：我們在求完dis之后對我們求的dis排序，這樣我們就可以快速的求出點對距離<=k的個數。

但是這樣就不可避免的要判重，為什么呢？

廢話你這樣排不就有可能把1操作的一部分點對先算了一遍，這樣明顯會導致答案變大。

那怎么辦呢？我們對于每一棵子樹，再刪掉我們通過2操作得到的點對即可。

（現將s刪掉，s的兒子dis[u]不變的情況下以u為起點bfs求點對，則這些點對就是在同一棵子樹當中被計算的重復的點對，減去即可。）

#include<cmath> #include<cstdio> #include<queue> #include<cctype> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N=10001; inline int read(){int X=0,w=0; char ch=0;while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } struct node{int w;int to;int nxt; }edge[N*2]; int cnt,n,k,head[N],q[N],dis[N],size[N],son[N],d[N],fa[N]; ll ans; bool vis[N]; void add(int u,int v,int w){cnt++;edge[cnt].to=v;edge[cnt].w=w;edge[cnt].nxt=head[u];head[u]=cnt;return; } int calcg(int st){int r=0,g,maxn=n;q[++r]=st;fa[st]=0;for(int l=1;l<=r;l++){int u=q[l];size[u]=1;son[u]=0;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(vis[v]||v==fa[u])continue;fa[v]=u;q[++r]=v;}}for(int l=r;l>=1;l--){int u=q[l],v=fa[u];if(r-size[u]>son[u])son[u]=r-size[u];if(son[u]<maxn)g=u,maxn=son[u];if(!v)break;size[v]+=size[u];if(size[u]>son[v])son[v]=size[u];}return g; } inline ll calc(int st,int L){int r=0,num=0;q[++r]=st;dis[st]=L;fa[st]=0;for(int l=1;l<=r;l++){int u=q[l];d[++num]=dis[u];for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;int w=edge[i].w;if(vis[v]||v==fa[u])continue;fa[v]=u;dis[v]=dis[u]+w;q[++r]=v;}}ll ecnt=0;sort(d+1,d+num+1);int l1=1,r1=num;while(l1<r1){if(d[l1]+d[r1]<=k){ecnt+=r1-l1;l1++;}else r1--;}return ecnt; } void solve(int u){int g=calcg(u);vis[g]=1;ans+=calc(g,0);for(int i=head[g];i;i=edge[i].nxt){int v=edge[i].to;int w=edge[i].w;if(!vis[v])ans-=calc(v,w);}for(int i=head[g];i;i=edge[i].nxt){int v=edge[i].to;if(!vis[v])solve(v);}return; } int main(){while(scanf("%d%d",&n,&k)!=EOF&&n+k){cnt=ans=0;memset(head,0,sizeof(head));memset(vis,0,sizeof(vis));for(int i=1;i<n;i++){int u=read();int v=read();int w=read();add(u,v,w);add(v,u,w);}solve(1);printf("%lld\n",ans);}return 0; }

?

轉載于:https://www.cnblogs.com/luyouqi233/p/8035910.html

總結

以上是生活随笔為你收集整理的POJ1741：Tree——题解+树分治简要讲解的全部內容，希望文章能夠幫你解決所遇到的問題。

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