[模板] 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

Sample Output

8

Source

LouTiancheng@POJ

题目大意
给定一棵带权树，和一个整数 $k$，选取一个点对(a,b)，使得 $a$ 与 $b$ 之间的距离不超过 $k$ 。问有多少个这样的点对?

大致思路
对于一个根节点 $v$，显然的，其子树中任意两个节点之间的路径，要么经过更节点 $v$，要么包含在其的一颗子树中。
对于一棵以 $v$ 为根的子树，求出其子树中每一个节点到根 $v$ 的距离。将这些距离从小到大排序，查找 $a[i] + a[j] \leq k$ 的点对。
递归求解，查找其子树。

以上就是大致思路。但还有一个明显的问题！
这样计算存在某子树中的节点经过树根 $v$ 后回到该子树中。我们要删去这种情况！（这两个点对是成立的，路径更长都成立了qwq，但因为在递归到 $v$ 的子树时会重复计算

具体步骤
1.将无根树转换为有根树，从树的重心开始进行点分治（防止退换成一条链，使复杂度变为 $O(n^3)$ ）
2.编写getdeep(int index,int father)函数计算以 $index$ 为根的子树节点到根的距离
3.编写calc(int v,int init)函数用来计算一个以 $v$ 为根节点的( $v$ 的距离初始为init)的排序好了的距离序列，这是可以用 $O(n)$ 的时间求出的。我们定义两个端点 $l,r$ 当 $l k$ 那么 $r–$
4.编写solve()函数进行分治。重复部分就减去calc(v,fa[v]->v.w)

Part 1:全局变量

struct Edge{
    int to;
    int w;
};

vector  map[MAXN];

bool vis[MAXN]; //标记数组 
int son[MAXN]; //子树节点数 
int f[MAXN]; //最大子树节点数 
int deep[MAXN]; //用于排序的deep
int d[MAXN]; //计算deep的数组 

Part 2:获得重心

void getroot(int index,int father){
    son[index] = 1; //计录子树大小（现在只有根节点) 
    f[index] = 0; //初始化最大子树值

    for(int i=0;i

void getdeep(int index,int father){
    deep[++deep[0]] = d[index]; //放入deep数组 deep[0]表示个数

    for(int i=0;i

int calc(int index,int init){

    d[index] = init; //初始化index到树根的距离 
    deep[0] = 0; //初始化个数 

    getdeep(index,0); //获取深度 

    sort(deep+1,deep+deep[0]+1); //排序 

    //如果deep[l] + deep[r] <=k
    //那么显然所有以l为左端点的点对 和均小于k

    int l = 1;
    int r = deep[0];
    int sum = 0;

    while(l

void solve(int index){
    ans += calc(index,0); //计算路径经过根符合条件的点对，此时Index为子树树根，故其距离为0 
    vis[index] = true; //标记 

    for(int i=0;i

int main(){
    while(scanf("%d%d",&n,&k)==2){
        if(!n && !k)
            break;

        ans = 0;  //初始化答案 
        root = 0; //初始化重心 
        memset(vis,0,sizeof(vis)); //初始化标记数组 

        for(int i=1;i<=n;i++)
            map[i].clear();

        for(int i=0;i