POJ 1741 Tree + POJ 1987 Distance Statistics【樹的點分治】

Tree

Time Limit: 1000MS Memory Limit: 30000K

Total Submissions: 13558 Accepted: 4367

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

題意：給出一棵樹所有邊的權值，詢問有多少點對間的距離小于等于K。

思路：參考http://blog.sina.com.cn/s/blog_6d5aa19a0100o73m.html

主要就是掌握對樹進行分治來降低複雜度的思想，将一顆無根樹化成有根樹，處理完以原樹之後，就進入到原樹的子樹中進行處理，即為分治。在這道題裡需要注意處理的是數對在根節點的一顆子樹裡和不在一顆子樹裡的情況，注意相減關系。

詳見代碼：

#pragma warning(disable:4996)
#include<stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
#define maxn 100006
#define inf 0x7fffffff
struct node
{
    int v,c;
    node(){}
    node(int v,int c):v(v),c(c){}
};
int n,m,K;
vector<node>g[maxn];
int size[maxn],Mson[maxn],root,deep[maxn],d[maxn];
bool vis[maxn];
int ans,sum;
//getRoot 得到以root為根的樹的重心，size[i]表示以i為根的樹的大小，Mson表示i的最大的子樹
void getRoot(int x,int p = ){
    size[x] = ;
    Mson[x] = ;
    int length = g[x].size();
    for (int i = ; i < length; i++)
    {
        int v = g[x][i].v;
        if(vis[v] ==  && v != p){
            getRoot(v,x);
            size[x] += size[v];
            Mson[x] = max(Mson[x],size[v]);
        }
    }
    Mson[x] = max(Mson[x],sum-size[x]);
    if(Mson[x] < Mson[root]) root = x;
}
//getDeep 得到子節點到根節點的deep數組
void getDeep(int x,int p = ){
    deep[++deep[]] = d[x];
    for (int i = ;i<g[x].size();i++)
    {
        int v = g[x][i].v;
        if(vis[v]== && v != p){
            d[v] = d[x] + g[x][i].c;
            getDeep(v,x);
        }
    }
}
// cal 計算以x為根的所有子樹裡滿足條件的點對，注意在後續需要減去在同一棵子樹裡的點對
int cal(int x,int dis = ){
    d[x] = dis;
    deep[] = ;
    getDeep(x,);
    sort(deep+,deep++deep[]);
    int cnt = ,l,r;
    for (l = ,r = deep[];l<r;)
    {
        if(deep[l] + deep[r] <= K)cnt += r-l,l++;
        else r--;
    }
    return cnt;
}
void work(int x){
    ans += cal(x);
    vis[x] = ;
    for (int i = ; i < g[x].size(); i++)
    {
        int v = g[x][i].v;
        if(vis[v])continue;
        // 在标記完父親節點（root）之後，就需要減去root的同一棵子樹中的答案
        ans -= cal(v,g[x][i].c);
        sum = size[v];
        root = ;
        getRoot(v,root);
        work(root);
    }
}
int main(){
    while (cin>>n>>m && n+m)
    {
        int u,v,c;
        //char s[5];
        for (int i = ; i < n-; i++)
        {
            //scanf("%d%d%d%s",&u,&v,&c,s);
            scanf("%d%d%d",&u,&v,&c);
            g[u].push_back(node(v,c));
            g[v].push_back(node(u,c));
        }
        //scanf("%d",&K);
        K = m;
        memset(vis,,sizeof vis);
        ans = ;    sum = n;
        Mson[] = inf;
        getRoot();
        work(root);
        printf("%d\n",ans);
        for (int i = ;i<=n;i++)g[i].clear();
    }
    return ;
}
           

對于1987,買一送一，改改輸入就可以了。