poj 1744 tree 树分治

时间：2023-05-16 10:59:08
Tree
Time Limit: 1000MS   Memory Limit: 30000K
     

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

树分治模板题；

分治算法在树的路径问题中的应用

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<set>

#include<map>

using namespace std;

#define LL long long

#define pi (4*atan(1.0))

#define eps 1e-8

#define bug(x)  cout<<"bug"<<x<<endl;

const int N=1e4+,M=2e6+,inf=1e9+;

const LL INF=1e18+,mod=1e9+;

struct is

{

    int v,w,nex;

}edge[N<<];

int head[N],edg;

void add(int u,int v,int w)

{

    edge[++edg]=(is){v,w,head[u]};head[u]=edg;

}

int son[N],msi[N],d[N];

int vis[N],deep[N];

int n,K,ans,root,sum;

void groot(int u,int fa)

{

    son[u]=,msi[u]=;

    for(int i=head[u];i!=-;i=edge[i].nex)

    {

        int v=edge[i].v;

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

        groot(v,u);

        son[u]+=son[v];

        msi[u]=max(msi[u],son[v]);

    }

    msi[u]=max(msi[u],sum-son[u]);

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

}

void gdeep(int x,int fa)

{

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

    for(int i=head[x];i!=-;i=edge[i].nex)

    {

        int v=edge[i].v;

        int w=edge[i].w;

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

        d[v]=d[x]+w;

        gdeep(v,x);

    }

}

int rootans(int x,int base)

{

    d[x]=base;deep[]=;

    gdeep(x,);

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

    int ans=,l=,r=deep[];

    while(l<r)

    {

        if(deep[l]+deep[r]<=K)

        {

            ans+=r-l;

            l++;

        }

        else r--;

    }

    return ans;

}

void dfs(int u)

{

    ans+=rootans(u,);

    vis[u]=;

    for(int i=head[u];i!=-;i=edge[i].nex)

    {

        int v=edge[i].v;

        int w=edge[i].w;

        if(vis[v])continue;

        ans-=rootans(v,w);

        root=;sum=son[v];

        groot(v,u);

        dfs(root);

    }

}

void init(int n)

{

    memset(head,-,sizeof(head));

    memset(msi,,sizeof(msi));

    memset(son,,sizeof(son));

    memset(d,,sizeof(d));

    memset(vis,,sizeof(vis));

    memset(deep,,sizeof(deep));

    sum=n;root=;edg=;

    msi[]=inf;

    ans=;

}

int main()

{

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

    {

        if(n==&&K==)break;

        init(n);

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

        {

            int u,v,w;

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

            add(u,v,w);

            add(v,u,w);

        }

        groot(,);

        dfs(root);

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

    }

    return ;

}

相关文章