POJ 1741 Tree 树分治

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

Sample Output

题意：

　　给你一个含有n个节点的树，每条边有权值，问你有多少点对最短路径不超过k

题解：

　　树分治入门题

　　推荐看09年ioi的论文

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std;

const int N = 1e5+, M = 1e2+, mod = 1e9+, inf = 1e9+;

typedef long long ll;

int n,m,root,t,ans,allnode,siz[N],K,head[N],vis[N],d[N];

int deep[N];//路径长度//deep[0]子节点个数

int f[N];//重心

struct edg{int to,next,v;}e[N * ];//前向星存边

void add(int u,int v,int w) {e[t].to=v;e[t].next=head[u];e[t].v=w;head[u]=t++;}//加边

//获取重心

void getroot(int x,int fa) {

    siz[x] = ;

    f[x] = ;

    for(int i=head[x];i;i=e[i].next) {

        int to = e[i].to;

        if(to == fa || vis[to]) continue;

        getroot(to,x);

        siz[x] += siz[to];

        f[x] = max(f[x] , siz[to]);

    }

    f[x] = max(allnode-siz[x] , f[x]);

    if(f[x] < f[root]) root = x;

}

void getdeep(int x,int fa) {//获取子树所有节点与根的距离

    deep[++deep[]] = d[x];

    for(int i=head[x];i;i=e[i].next) {

        int to = e[i].to;

        if(to == fa || vis[to]) continue;

        d[to] = d[x] + e[i].v;

        getdeep(to,x);

    }

}

int cal(int x,int now) {//计算当前以重心x的子树下，所有情况的答案

    d[x]=now;deep[]=;

    getdeep(x,);

    sort(deep+,deep+deep[]+);

    int all = ;

    for(int l=,r=deep[];l<r;) {

        if(deep[l]+deep[r] <= K) {all += r-l;l++;}

        else r--;

    }

    return all;

}

void work(int x) {//以x为重心进行计算

    vis[x] = ;

    ans+=cal(x,);

    for(int i=head[x];i;i=e[i].next) {

        int to = e[i].to;

        if(vis[to]) continue;

        ans -= cal(to,e[i].v);

        allnode = siz[to];

        root=;

        getroot(to,x);

        work(root);

    }

}

int main()

{

    while(~scanf("%d%d",&n,&K)) {

        if(!n&&!m) break;

        memset(head,,sizeof(head));

        memset(vis,,sizeof(vis));

        t = ;

        for(int i=;i<n;i++) {

            int a,b,c;

            scanf("%d%d%d",&a,&b,&c);

            add(a,b,c) , add(b,a,c);

        }

        root=ans=;

        allnode=n;f[]=inf;

        getroot(,);

        work(root);

        printf("%d\n",ans);

    }

}

秒客网

POJ 1741 Tree 树分治

相关文章