POJ 1741 Tree
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的点对，则先在所有子数中寻找满足要求的点对，个数记为X，再寻找路径经过根，且距离小于k的点对，个数记为Y，最终结果为X+Y。
（1）每次递归根的寻找--树的重心
在点的分置过程中，第一步就是选取一个根，根据该根将整棵树划分为不同的子树。如果这个点是任意选取的，很有可能会使算法退化，极端情况是整棵树呈链状，若每次都选取链顶端节点作为根，则复杂度从logN退化为N。
树重心的定义：树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。
所以在分治的过程中，每一次都将根选为当前树的重心，可以提高算法速率。
（2）通过根的路径距离计算
我们首先通过dfs计算每个节点t到根的距离dis[t],则i，j两个节点间距离为dis[i]+dis[j],并且i，j不属于同一个子树。
如果这样考虑问题会变得比较麻烦，我们可以考虑换一种角度：
- 设X为满足
i<j且dis[i]+dis[j]<=K的数对(i,j)的个数 - 设Y为满足
i<j，Depth[i]+Depth[j]<=K且Belong[i]=Belong[j]数对(i,j)的个数
那么我们要统计的量便等于X-Y
（3）通过O(n)复杂度寻找满足要求点对--排序的应用
求X、Y的过程均可以转化为以下问题：
已知dis[1],dis[2],...dis[m]，求满足i<j且dis[i]+dis[j]<=K的数对(i,j)的个数
对于这个问题，我们先将dis从小到大排序。通过两个指针l,r，l头到尾扫描，r从尾向头扫描，如果dis[l]+dis[r]<=K,l++,且符合条件点对个数增加(r-l)，因为如果当前l与r的组合满足条件，l与l+1,l+2...r-1的组合也必然满足条件；否则r--。
数据结构与算法设计及其主要代码段
树的分治
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. 算法复杂度
设递归最大层数为L，因为每一层的时间复杂度均为“瓶颈”——排序的时间复杂度O(NlogN)，所以总的时间复杂度为O(L*NlogN)
参考http://blog.csdn.net/u010660276/article/details/44920725
B. 运行时间
内存 2944kB， 时间: 93ms（数据来自openjudge）
心得体会与总结
- 本题好难。。。知识点很多，基于点的分治，重心求解，O（n）扫描求解点对
- 细节很多，递归终止条件，父节点的传入等。
