[原创]POJ 1741 Tree [点分治入门题]【分治】

2017-07-17 20:37:58 Tabris_ 阅读数：375

博客爬取于2020-06-14 22:39:38
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/75267826

题目链接:http://poj.org/problem?id=1741
——————————————————————————————————————————
Tree
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 22808 Accepted: 7542
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

——————————————————————————————————————————
题目大意：
给你一棵树，问你两点间距离不超过k的点对个数

最好去看论文===>戳这里

考虑到每颗树上 统计路径经过树根的点对,

很容易想到 处理一遍子树 记录每个节点到达根节点的距离,
然后就变成了

给定一个序列,统计两个数加和不超过k的数对的个数
尺取法就能做了

但是注意这里计算之后会有重复的情况

这里写图片描述

比如当前计算的是根为1 的情况 这个时候如果k比较大 那么还会把<4,6>的情况 给计算上,但是<4,6>的路径是 4->5->6

所以我们还需要减去以1的儿子节点为根的时候的情况

并不断递归下去找一颗颗子树.

但是这样下去的话 能发现 不断递归下去的话
复杂度依赖于 树的形态
如果树是严格平衡的话递归下去的复杂读就是O(log⁡n)O(\log n)
如果树的形态是一条链的情况 就会变成O(n)O(n)

于是这里 采取树的重心 作为树根，这样下去的话 能保证 递归下去的深度最低 最终做到复杂度O(log⁡n)(\log n) [证明请移步国家队论文↑]

注意: 对于 递归下去的子树 为了保证复杂读 也要再次采用重心为根来做,

于是最终复杂度就变为O(nlog⁡2n)O(n\log^2n)

其中一个log⁡\log 为分治 向下递归的复杂度
另一个log⁡\log 为统计的时候 需要保证序列单调的 排序复杂度

附本题代码
——————————————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
# include <stdio.h>
# include <vector>
# include <iostream>
# include <algorithm>
# include <string.h>

using namespace std;

const int N   = 20000+7;

/*********************************/

int n,k,ans;

bool vis[N];
int d[N],f[N];

struct edge{
    int to,next;
    int w;
}G[N<<1];
int head[N],tot;
void add(int u,int v,int w=0){
    G[tot].w=w,G[tot].to=v,G[tot].next=head[u],head[u]=tot++;
}

/********重心 begin********/
int sz[N],dn[N],siz,zx;

void getzx(int u,int fa=0){
    sz[u]=1;dn[u]=0;
    for(int i=head[u],to;i!=-1;i=G[i].next){
        to = G[i].to;
        if(to == fa||vis[to]) continue;
        getzx(to,u);
        sz[u]+=sz[to];
        dn[u]=max(dn[u],sz[to]);
    }
    dn[u]=max(dn[u],siz-sz[u]);
    if(dn[u]<dn[zx]) zx=u;
}

/*********重心 end********/
/**
d[] 为当前节点到当前树根的距离
f[] 就是记录当前处理的子树的每个节点的d[]
*/
void getd(int u,int fa=0){
    f[++f[0]] = d[u];
    for(int i=head[u],to;i!=-1;i=G[i].next){
        to=G[i].to;
        if(to==fa||vis[to]) continue;
        d[to]=d[u]+G[i].w;
        getd(to,u);
    }
}

int cal(int u,int w){
    d[u]=w; f[0]=0;int sum = 0;
    getd(u); sort(f+1,f+f[0]+1);
    for(int l=1,r=f[0];l<r;){
        if(f[l]+f[r]<=k){sum+=r-l;l++;}
        else r--;
    }
    return sum;
}

void solve(int u){
    ans+=cal(u,0);
    vis[u]=1;
    for(int i=head[u],to;i!=-1;i=G[i].next){
        to=G[i].to;
        if(vis[to]) continue;
        ans-=cal(to,G[i].w);
        siz=sz[to],zx=0;getzx(to);
        solve(zx);
    }
}

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

        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        dn[0]=n*10;zx=0;tot=0;

        for(int i=1,u,v,w;i<n;i++){
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);add(v,u,w);
        }

        siz = n; getzx(1);
        ans = 0;solve(zx);

        printf("%d\n",ans);
    }
    return 0;
}