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,买一送一，改改输入就可以了。