Tree

发表于 | 分类于 |
字数统计: 1.3k | 阅读时长 ≈ 6

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

思路

假定选择一点1为根，那其他点到根的最短距离就有两种情况。

其一，它们在根的不同分支上，那他们的最近距离就是它们到它们的最近公共祖先的距离和。

其二，如果它们在根的同一个分支上，那么最近距离就是它们之间的距离。

我们分析到这，先求出其他点到根1点的距离用一个dfs求出，放进一个数组里a[maxn]，对它排一个序，这里面任意两点只有以上两种情况，来自1同一个分支，或是不同分支，而我们求得方案数一定是来自不同分支。直接求不好求，我们可以先求出

A：a[i]+a[j] <=k的方案数（不管i，j是否来自同一个分支）这种点对是对答案有贡献的。

B：a[i]+a[j]<=k的方案数（i,j来自同一个分支）同一分支，则a[i]+a[j]不是i,j之间的真是距离。

所以代码中是先把A,B的情况同时计算了，然后减去B中的方案数。

B怎么求呢？我们只要在求a数组的过程在A的前提下加一个边的权值，这样就相当于控制i,j两条边的方向就是来自于这一条边的方向。（这里看代码细细体会）

排序时间复杂度为$O(N\log(N))$递归深度为$\log(N)$，整体时间复杂度为$O(Nlog^2(N))$

代码

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
99
100
101
102
103
104
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
#define N 100010

//输入增强，减少输入时间。
inline void in(int &x) {
    x = 0; int f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    x *= f;
}

int n, k, d[N], cnt, head[N], ans;
int vis[N], siz[N];
//孩子兄弟表示法
struct edge {
	int to, nxt, v;
}e[N<<1];

void ins(int u, int v, int w) {
	e[++cnt] = (edge) {v, head[u], w};
	head[u] = cnt;
}

int now_sz = inf, root = 0, sz;
//找到树的重心
void find_root(int u, int fa) {
	siz[u] = 1;
	int res = 0;
	for(int i = head[u]; i; i = e[i].nxt) {
		if(vis[e[i].to] || e[i].to == fa) continue;
		int v = e[i].to;
		find_root(v, u);	//递归获取子树孩子结点数量
		siz[u] += siz[v];
		res = max(res, siz[v]);	//保存最大的子树结点数。
	}
	res = max(res, sz - siz[u]); //看看除了这颗子树的结点数和这颗子树的结点数那个更多， 其实就是让以该点为重心的化，这颗树个个分支更加平均。

	if(res < now_sz) now_sz = res, root = u;	//如果以该点为重心能使的使得个分支更加平均，更新重心。
}
//a保存每个结点到重心u的距离。
int a[N], tot;
//递归获取u的子结点到u的距离。
void get_dis(int u, int fa) {
	a[++tot] = d[u]; //将所有的距离保存
	for(int i = head[u]; i; i = e[i].nxt) {
		if(vis[e[i].to] || e[i].to == fa) continue;
		int v = e[i].to;
		d[v] = d[u] + e[i].v;
		get_dis(v, u);
	}
}

//这里是计算所有子树中到u的距离和小于k的点对（i，j）的数量，这里同时统计了位于一个子树和不同子树的点对， 位于同一个子树的后面会减掉。
int solve(int u, int dis) {
	d[u] = dis; tot = 0;
	get_dis(u, u);
	sort(a + 1, a + tot + 1); 
	int l = 1, r = tot, res = 0;
	for(; l < r; ++l) {
		while(l < r && a[l] + a[r] > k) --r;
		if(l < r) res += r - l;
	}
	return res;
}

void dfs(int u) {
	vis[u] = 1;
	ans += solve(u, 0); //以0为重心计算点对数量
	for(int i = head[u]; i; i = e[i].nxt) {
		if(vis[e[i].to]) continue;
		int v = e[i].to;
		ans -= solve(v, e[i].v);  //这里就是减去同一子树中点对贡献的答案
		now_sz = inf, root = 0; sz = siz[v];
		find_root(v, 0); //分治处理子树
		dfs(root);
	}
}

int main() {
	while(~scanf("%d%d", &n, &k) && n && k) {
		ans = 0; cnt = 0; 
		memset(head, 0, sizeof(head));
		memset(vis, 0, sizeof(vis));
		for(int i = 1; i < n; ++i) {
			int u, v, w; in(u), in(v), in(w);
			ins(u, v, w), ins(v, u, w); //保存u->v,v->u两条边
		}
		dfs(1);
		printf("%d\n", ans);
	}
}

0%