Description
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
1
2
3
4
5
6
5 4
1 2 3
1 3 1
1 4 2
3 5 1
0 0
Sample Output
8
1
8
問題分析與解題思路
本題我采用基于點的樹的分治進行求解
轉自漆子超論文算法合集之《分治算法在樹的路徑問題中的應用》
我們要尋找所有距離小于k的點對，則先在所有子數(shù)中尋找滿足要求的點對瑰排，個數(shù)記為X琢歇，再尋找路徑經過根佛吓，且距離小于k的點對蛇更，個數(shù)記為Y，最終結果為X+Y座慰。
（1）每次遞歸根的尋找--樹的重心
在點的分置過程中陨舱，第一步就是選取一個根翠拣，根據(jù)該根將整棵樹劃分為不同的子樹版仔。如果這個點是任意選取的，很有可能會使算法退化误墓，極端情況是整棵樹呈鏈狀蛮粮，若每次都選取鏈頂端節(jié)點作為根，則復雜度從logN退化為N谜慌。
樹重心的定義：樹的重心也叫樹的質心然想。找到一個點,其所有的子樹中最大的子樹節(jié)點數(shù)最少,那么這個點就是這棵樹的重心,刪去重心后，生成的多棵樹盡可能平衡欣范。
所以在分治的過程中变泄，每一次都將根選為當前樹的重心，可以提高算法速率恼琼。
（2）通過根的路徑距離計算
我們首先通過dfs計算每個節(jié)點t到根的距離dis[t],則i妨蛹，j兩個節(jié)點間距離為dis[i]+dis[j],并且i，j不屬于同一個子樹晴竞。
如果這樣考慮問題會變得比較麻煩蛙卤，我們可以考慮換一種角度：
- 設X為滿足
i<j且dis[i]+dis[j]<=K的數(shù)對(i,j)的個數(shù) - 設Y為滿足
i<j，Depth[i]+Depth[j]<=K且Belong[i]=Belong[j]數(shù)對(i,j)的個數(shù)
那么我們要統(tǒng)計的量便等于X-Y
（3）通過O(n)復雜度尋找滿足要求點對--排序的應用
求X噩死、Y的過程均可以轉化為以下問題：
已知dis[1],dis[2],...dis[m]颤难，求滿足i<j且dis[i]+dis[j]<=K的數(shù)對(i,j)的個數(shù)
對于這個問題，我們先將dis從小到大排序已维。通過兩個指針l,r行嗤，l頭到尾掃描，r從尾向頭掃描垛耳，如果dis[l]+dis[r]<=K,l++,且符合條件點對個數(shù)增加(r-l)栅屏，因為如果當前l(fā)與r的組合滿足條件，l與l+1,l+2...r-1的組合也必然滿足條件艾扮；否則r--既琴。
數(shù)據(jù)結構與算法設計及其主要代碼段
樹的分治
void work(int x)
{
ans+=cal(x,0);
vis[x]=1;
for(int i=head[x];i;i=e[i].next)
{
if(vis[e[i].to])continue;
ans-=cal(e[i].to,e[i].v);
sum=son[e[i].to];
root=0;
getroot(e[i].to,root);
work(root);
}
}
尋找樹的重心
void getroot(int x,int fa)
{
son[x]=1;f[x]=0;
for(int i=head[x];i;i=e[i].next)
{
if(e[i].to==fa||vis[e[i].to])continue;
getroot(e[i].to,x);
son[x]+=son[e[i].to];
f[x]=max(f[x],son[e[i].to]);
}
f[x]=max(f[x],sum-son[x]);
if(f[x]<f[root])root=x;
}
計算以u為根的子樹中有多少點對的距離小于等于K
int cal(int x,int now)
{
d[x]=now;deep[0]=0;
getdeep(x,0);
sort(deep+1,deep+deep[0]+1);
int t=0,l,r;
for(l=1,r=deep[0];l<r;)
{
if(deep[l]+deep[r]<=K){t+=r-l;l++;}
else r--;
}
return t;
}
程序運行結果及分析
A. 算法復雜度
設遞歸最大層數(shù)為L，因為每一層的時間復雜度均為“瓶頸”——排序的時間復雜度O(NlogN)泡嘴，所以總的時間復雜度為O(L*NlogN)
參考http://blog.csdn.net/u010660276/article/details/44920725
B. 運行時間
內存 2944kB甫恩， 時間: 93ms（數(shù)據(jù)來自openjudge）
心得體會與總結
- 本題好難。酌予。磺箕。知識點很多奖慌，基于點的分治，重心求解松靡，O（n）掃描求解點對
- 細節(jié)很多简僧，遞歸終止條件，父節(jié)點的傳入等雕欺。
