POJ 1741 Tree （点分治）

Tree

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 20816		Accepted: 6820

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

Source

LouTiancheng@POJ

【分析】

给一棵边带权树，问两点之间的距离小于等于K的点对有多少个。

将无根树转化成有根树进行观察。满足条件的点对有两种情况：两个点的路径横跨树根，两个点位于同一颗子树中。

如果我们已经知道了此时所有点到根的距离a[i]，a[x] + a[y] <= k的(x, y)对数就是结果，这个可以通过排序之后O(n)的复杂度求出。然后根据分治的思想，分别对所有的儿子求一遍即可，但是这会出现重复的——当前情况下两个点位于一颗子树中，那么应该将其减掉（显然这两个点是满足题意的，为什么减掉呢？因为在对子树进行求解的时候，会重新计算）。

在进行分治时，为了避免树退化成一条链而导致时间复杂度变为O(N^2)，每次都找树的重心，这样，所有的子树规模就会变的很小了。时间复杂度O(Nlog^2N)。

树的重心的算法可以线性求解。

#include <iostream>

#include <cstring>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <time.h>

#include <string>

#include <map>

#include <stack>

#include <vector>

#include <set>

#include <queue>

#define met(a,b) memset(a,b,sizeof a)

#define pb push_back

#define lson(x) ((x<<1))

#define rson(x) ((x<<1)+1)

using namespace std;

typedef long long ll;

const int N=1e5+;

const int M=1e6+;

int n,m,k,tot,size,root,ans;

int head[N],s[N],f[N],d[N];

bool done[N];

vector<int>dep;

struct man{

    int to,next,l;

}edg[N*];

void add(int u,int v,int l){

    edg[tot].to=v;edg[tot].l=l;edg[tot].next=head[u];head[u]=tot++;

}

void getroot(int u,int fa){

    s[u]=;f[u]=;

    for(int i=head[u];i!=-;i=edg[i].next){

        int v=edg[i].to;

        if(v!=fa&&!done[v]){

            getroot(v,u);

            s[u]+=s[v];

            f[u]=max(f[u],s[v]);

        }

    }

    f[u]=max(f[u],size-s[u]);

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

}

void getdep(int u,int fa){

    dep.push_back(d[u]);

    s[u]=;

    for(int i=head[u];i!=-;i=edg[i].next){

        int v=edg[i].to;

        if(v!=fa&&!done[v]){

            d[v]=d[u]+edg[i].l;

            getdep(v,u);

            s[u]+=s[v];

        }

    }

}

int calc(int u,int init){

    dep.clear();

    d[u]=init;

    getdep(u,);

    sort(dep.begin(),dep.end());

    int ret=;

    for(int l=,r=dep.size()-;l<r; ){

        if(dep[l]+dep[r]<=k)ret+=r-l++;

        else r--;

    }

    return ret;

}

void work(int u){

    ans+=calc(u,);

    done[u]=true;

    for(int i=head[u];i!=-;i=edg[i].next){

        int v=edg[i].to;

        if(!done[v]){

            ans-=calc(v,edg[i].l);

            f[]=size=s[v];

            getroot(v,root=);

            work(root);

        }

    }

}

int main(){

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

        tot=ans=;f[]=size=n;

        met(head,-);met(done,false);

        int u,v,l;

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

            scanf("%d%d%d",&u,&v,&l);

            add(u,v,l);add(v,u,l);

        }

        getroot(,root=);

        work(root);

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

    }

    return ;

}

秒客网

POJ 1741 Tree （点分治）

相关文章