[模板] POJ-1741 Tree


1741 – 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

LouTiancheng@POJ


题目大意
给定一棵带权树,和一个整数 $k$,选取一个点对(a,b),使得 $a$ 与 $b$ 之间的距离不超过 $k$ 。问有多少个这样的点对?

 

大致思路
对于一个根节点 $v$,显然的,其子树中任意两个节点之间的路径,要么经过更节点 $v$,要么包含在其的一颗子树中。
对于一棵以 $v$ 为根的子树,求出其子树中每一个节点到根 $v$ 的距离。将这些距离从小到大排序,查找 $a[i] + a[j] \leq k$ 的点对。
递归求解,查找其子树。

以上就是大致思路。但还有一个明显的问题!
这样计算存在某子树中的节点经过树根 $v$ 后回到该子树中。我们要删去这种情况!(这两个点对是成立的,路径更长都成立了qwq,但因为在递归到 $v$ 的子树时会重复计算

 

具体步骤
1.将无根树转换为有根树,从树的重心开始进行点分治(防止退换成一条链,使复杂度变为 $O(n^3)$ )
2.编写getdeep(int index,int father)函数计算以 $index$ 为根的子树节点到根的距离
3.编写calc(int v,int init)函数用来计算一个以 $v$ 为根节点的( $v$ 的距离初始为init)的排序好了的距离序列,这是可以用 $O(n)$ 的时间求出的。我们定义两个端点 $l,r$ 当 $l k$ 那么 $r–$
4.编写solve()函数进行分治。重复部分就减去calc(v,fa[v]->v.w)

 

Part 1:全局变量

struct Edge{
    int to;
    int w;
};

vector  map[MAXN];

bool vis[MAXN]; //标记数组 
int son[MAXN]; //子树节点数 
int f[MAXN]; //最大子树节点数 
int deep[MAXN]; //用于排序的deep
int d[MAXN]; //计算deep的数组 

 

Part 2:获得重心

void getroot(int index,int father){
    son[index] = 1; //计录子树大小(现在只有根节点) 
    f[index] = 0; //初始化最大子树值

    for(int i=0;i

 

Part 3:获取距离

void getdeep(int index,int father){
    deep[++deep[0]] = d[index]; //放入deep数组 deep[0]表示个数

    for(int i=0;i

 

Part 4:计算函数

int calc(int index,int init){

    d[index] = init; //初始化index到树根的距离 
    deep[0] = 0; //初始化个数 

    getdeep(index,0); //获取深度 

    sort(deep+1,deep+deep[0]+1); //排序 

    //如果deep[l] + deep[r] <=k
    //那么显然所有以l为左端点的点对 和均小于k

    int l = 1;
    int r = deep[0];
    int sum = 0;

    while(l

 

点分治

void solve(int index){
    ans += calc(index,0); //计算路径经过根符合条件的点对,此时Index为子树树根,故其距离为0 
    vis[index] = true; //标记 

    for(int i=0;i

 

Part 5:主函数

int main(){
    while(scanf("%d%d",&n,&k)==2){
        if(!n && !k)
            break;

        ans = 0;  //初始化答案 
        root = 0; //初始化重心 
        memset(vis,0,sizeof(vis)); //初始化标记数组 

        for(int i=1;i<=n;i++)
            map[i].clear();

        for(int i=0;i