poj 1741 Tree (树的分治）

Tree

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 30928		Accepted: 10351

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。

树分治经典题。

以下删改自sdj222555的****博客。

需要分治。可以看09年漆子超的论文。本题用到的是关于点的分治。

一个重要的问题是，为了防止退化，所以每次都要找到树的重心然后分治下去，所谓重心，就是删掉此结点后，剩下的结点最多的树结点个数最小。

每次分治，我们首先算出重心，为了计算重心，需要进行两次dfs，第一次把以每个结点为根的子树大小求出来，第二次是从这些结点中找重心。

当然在一次dfs过程中也能做到。另外虽然说不记忆化也能做到，但还是用个son数组记忆下吧。

另外，无向图的dfs不需要像我之前一样遇一个点打个vis标记，dfs定义成dfs(u,pa)，保存该点的父亲就不会返回去啦。

找到重心后，需要统计所有结点到重心的距离，看其中有多少对小于等于K。

这里采用的方法就是把所有的距离存在一个数组里（不要忘了重心到自己的），进行快速排序，这是nlogn的，然后用一个经典的相向搜索O(n)时间内解决。

但是这些求出来满足小于等于K的里面只有那些路径经过重心的点对才是有效的，也就是说在同一颗子树上的肯定不算数的。所以对每颗子树，把子树内部的满足条件的点对减去。

最后的复杂度是n logn logn 其中每次快排是nlogn 而递归的深度为logn。

代码实现比较复杂，今后有时间还是可以再敲一次。

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <string>

#include <cmath>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

typedef long long ll;

const int maxn=;

const int inf=;

int n,k;

int to[maxn*+];

int w[maxn*+];

int next[maxn*+];

int head[maxn+];

int cnt;

void addedge(int a,int b,int c)

{

    to[cnt]=b;w[cnt]=c;

    next[cnt]=head[a];head[a]=cnt++;

}

int ans;

int mins,root;

int son[maxn+];

int vis[maxn+];

int depth[maxn+];

int dis[maxn+],tot;

void getroot(int u,int pa,int num)//求重心

{

    int maxs=;

    son[u]=;

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

    {

        int l=to[i];

        if(l!=pa&&!vis[l])

        {

            getroot(l,u,num);

            maxs=std::max(maxs,son[l]);

            son[u]+=son[l];

        }

    }

    maxs=std::max(maxs,num-son[u]);

    if(maxs<mins)

    {

        mins=maxs;

        root=u;

    }

}

void getdepth(int u,int pa)//通过深度得出需要的dis值

{

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

    {

        int l=to[i];

        if(l!=pa&&!vis[l])

        {

            depth[l]=depth[u]+w[i];

            dis[tot++]=depth[l];

            getdepth(l,u);

        }

    }

}

int calc(int u,int pa,int d)

{

    depth[u]=;

    tot=;

    dis[tot++]=;

    getdepth(u,pa);

    int ret=;

    std::sort(dis,dis+tot);

    int i=,j=tot-;

    while(i<j)//经典的相向搜索

    {

        while(dis[i]+dis[j]+d*>k&&i<j)

            j--;

        ret+=j-i;

        i++;

    }

    return ret;

}

void dfs(int x,int num)

{

    mins=inf;

    getroot(x,-,num);//找重心

    ans+=calc(root,-,);//计算整棵树符合条件的对数

    for(int i=head[root];i!=-;i=next[i])

    {

        int l=to[i];

        if(!vis[l])

            ans-=calc(l,root,w[i]);//减去每棵子树符合条件的对数

    }

    vis[root]=;//打标记

    for(int i=head[root];i!=-;i=next[i])

    {

        int l=to[i];

        if(!vis[l])

            dfs(l,son[l]);//向子树递归

    }

}

int main()

{

    while(scanf("%d%d",&n,&k),n||k)

    {

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

        cnt=;

        for(int i=,a,b,c;i<=n-;i++)

        {

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

            addedge(a,b,c);

            addedge(b,a,c);

        }

        memset(vis,,sizeof(vis));

        ans=;

        dfs(,n);

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

    }

    return ;

}

秒客网

poj 1741 Tree (树的分治）

相关文章