美文网首页
POJ 1741 Tree

POJ 1741 Tree

作者: lily_blog | 来源:发表于2017-11-05 18:54 被阅读0次

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
1
2
3
4
5
6
5 4
1 2 3
1 3 1
1 4 2
3 5 1
0 0
Sample Output
8
1
8

问题分析与解题思路

本题我采用基于点的树的分治进行求解


转自漆子超论文算法合集之《分治算法在树的路径问题中的应用》

我们要寻找所有距离小于k的点对,则先在所有子数中寻找满足要求的点对,个数记为X,再寻找路径经过根,且距离小于k的点对,个数记为Y,最终结果为X+Y。

(1)每次递归根的寻找--树的重心

在点的分置过程中,第一步就是选取一个根,根据该根将整棵树划分为不同的子树。如果这个点是任意选取的,很有可能会使算法退化,极端情况是整棵树呈链状,若每次都选取链顶端节点作为根,则复杂度从logN退化为N。

树重心的定义:树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后,生成的多棵树尽可能平衡。

所以在分治的过程中,每一次都将根选为当前树的重心,可以提高算法速率。

(2)通过根的路径距离计算

我们首先通过dfs计算每个节点t到根的距离dis[t],则i,j两个节点间距离为dis[i]+dis[j],并且i,j不属于同一个子树。

如果这样考虑问题会变得比较麻烦,我们可以考虑换一种角度:

  • 设X为满足i<jdis[i]+dis[j]<=K的数对(i,j)的个数
  • 设Y为满足i<jDepth[i]+Depth[j]<=KBelong[i]=Belong[j]数对(i,j)的个数

那么我们要统计的量便等于X-Y

(3)通过O(n)复杂度寻找满足要求点对--排序的应用

求X、Y的过程均可以转化为以下问题:
已知dis[1],dis[2],...dis[m],求满足i<jdis[i]+dis[j]<=K的数对(i,j)的个数

对于这个问题,我们先将dis从小到大排序。通过两个指针l,r,l头到尾扫描,r从尾向头扫描,如果dis[l]+dis[r]<=K,l++,且符合条件点对个数增加(r-l),因为如果当前l与r的组合满足条件,ll+1,l+2...r-1的组合也必然满足条件;否则r--

数据结构与算法设计及其主要代码段

树的分治

void work(int x)
{
    ans+=cal(x,0);
    vis[x]=1;
    for(int i=head[x];i;i=e[i].next)
    {
        if(vis[e[i].to])continue;
        ans-=cal(e[i].to,e[i].v);
        sum=son[e[i].to];
        root=0;
        getroot(e[i].to,root);
        work(root);
    }
}

寻找树的重心

void getroot(int x,int fa)
{
    son[x]=1;f[x]=0;
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].to==fa||vis[e[i].to])continue;
        getroot(e[i].to,x);
        son[x]+=son[e[i].to];
        f[x]=max(f[x],son[e[i].to]);
    }
    f[x]=max(f[x],sum-son[x]);
    if(f[x]<f[root])root=x;
}

计算以u为根的子树中有多少点对的距离小于等于K

int cal(int x,int now)
{
    d[x]=now;deep[0]=0;
    getdeep(x,0);
    sort(deep+1,deep+deep[0]+1);
    int t=0,l,r;
    for(l=1,r=deep[0];l<r;)
    {
        if(deep[l]+deep[r]<=K){t+=r-l;l++;}
        else r--;
    }
    return t;
}

程序运行结果及分析

A. 算法复杂度
设递归最大层数为L,因为每一层的时间复杂度均为“瓶颈”——排序的时间复杂度O(NlogN),所以总的时间复杂度为O(L*NlogN)
参考http://blog.csdn.net/u010660276/article/details/44920725

B. 运行时间

内存 2944kB, 时间: 93ms(数据来自openjudge)

心得体会与总结

  1. 本题好难。。。知识点很多,基于点的分治,重心求解,O(n)扫描求解点对
  2. 细节很多,递归终止条件,父节点的传入等。

相关文章

  • POJ 1741 Tree

    Description Give a tree with n vertices,each edge has a l...

  • POJ 1741 Tree

    难度 尚未评定Description给定一颗有个节点的树,每条边有一个权值。树上两个节点和之间的路径长度就是路径上...

  • POJ 1741 Tree 点分树题解

    Openjudge原题链接 POJ原题链接 题意输入树的各边及其长度,求路径小于等于k的点对数目 题解目标:寻找长...

  • POJ_1741 男人八题

    1.题目相关 标签:树分治 题目地址:http://poj.org/problem?id=1741 题目大意:见论...

  • (动态)点分治

    POJ-1741(带边权 && 边权可以为负值的树) 复杂度: O(nlog²n) Distance in Tre...

  • POJ1308(Is It A Tree?)

    链接:https://vjudge.net/problem/POJ-1308思路:放在并查集专题的,思路是每次合并...

  • Poj 2255 Tree Recovery

    关于二叉树的前中后序遍历的很好一道题 题目:根据二叉树的前序和中序序列来重建二叉树,输出其后序序列image.pn...

  • 1741

    现在我是在外面,在去超市的路上,我本来出来是为了一拿个快递,二去超市买一点中午想吃的菜自己做,但在出门之前我一直在...

  • 1741

    2022.01.05 星期三 晴 昨晚云灿忘了带签字的资料回来,今早要去学校给她签字。早晨起来我给云灿说早...

  • Chapter9——图——最小生成树

    1. 题目列表 POJ1789(prim算法) POJ2485(prim) POJ1258(prim) POJ30...

网友评论

      本文标题:POJ 1741 Tree

      本文链接:https://www.haomeiwen.com/subject/wtshmxtx.html