Tree

Description

Input

Output

Sample Input

5 4
1 2 3
1 3 1
1 4 2
3 5 1
0 0

Sample Output

8

Source

题目的大概意思就是给定一颗带权树，求树上小于K的路径条数。点分治裸题。

那么怎么做呢？我们可以很快发现每一条路径只有两种情况：经过根、不经过根。而树又是递归定义的。自然而然的就想到了可以分治：对于每一棵子树计算出过根满足条件的路径条数，然后对这棵子树的根下面的每一棵子树分治下去。就求出了所有路径！

于是对于每一次子树操作，我们一次dfs出子树中所有节点到根的深度（注意：包括根节点本身哦，继续看下去就明白啦）。然后问题便成了求数组中满足和<=k的二元组个数，如果二元组中有一个数为根节点深度——0，表示这是从根节点出发的路径。我们可以先对数组排序(我懒直接n log n Sort)。然后定义两个指针L,R，初值L=数组开始，R=数组结尾。每当深度数组（假设为d）d[L] + d[R] <= k 时，因为数组具有单调性，可以知道此时满足条件的二元组有R-L个。此时累加答案并且把L指针右移。若不满足条件则把R指针左移。这样查找复杂度是O（N）的。

但是我们多算了一些情况在内！如这张绝对不是画图画的图——

可以看出图中黄线所示的路径也被算了进去！d[4]+d[3]=11<12满足了条件。但是它并不符合题意，那么我们怎么办呢？这时我们又灵机一动：可以再对子树进行一次上述操作，并把根节点起始深度设置为子树根到原树根连边的边权。这样就能求出经过原树根绕一圈回来的符合条件路径的条数。我们按上述操作查找出原树的ans后再对每一棵子树进行操作，用原树的ans减去子树的ans和就得到了一层递归的答案！只要逐层答案累加，就得到了解！

但是这个算法有一个缺陷——如果在某些极端情况下树层数非常的高，复杂度将不会被保证，查找操作的复杂度甚至会退化成线性（一条链）于是我们想到了一个绝佳的方法：每一次操作用树的重心作为树的树根！这个想法听起来很疯但是也非常巧妙的保证了复杂度。

我们注意到每当我们进行完一层分治以后，我们需要对每一个单独的子树进行新一轮分治。而子树之间是不会相互影响的，子树之上的原树也已经处理完了，指定根节点既不会影响以前的结果也不会影响其他子树的结果，我们当然可以指定一个根从它开始。那么怎么找到这个树的重心呢？树的重心定义为无根树中指定为根后所有子树中最大的子树最小的点。我们只需要先从原根开始dfs出每一个点下子树大小，那么一个点下所有节点都是它作为根后的子树节点，同样的，一个点原来的父亲也会变成子树节点，这棵子树的大小为 ：总节点个数-当前点子树大小。我们只需要对每一个点这样取换根后最大子树的大小，再在其中选出值最小的点就找到了重心。

如果你没有看懂，可以看看这篇：点我点我！我是“这篇”

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define min(a, b) (a > b ? b : a)
#define max(a, b) (a > b ? a : b)
using namespace std; 
const int maxn = 1e4 + 100;
struct edge {
	int v, w, next;
}e[maxn << 1];
int head[maxn], cnt, root[maxn], son[maxn], h[maxn];
int depth[maxn], d[maxn], dcnt, ans;
int n, k;
bool vis[maxn];
void adde(const int &u, const int &v, const int &w) {
	e[cnt] = (edge) {v, w, head[u]} ;
	head[u] = cnt++;
}
void getroot(int u, int fa, int tot, int & root) {
	son[u] = 1, h[u] = 0;
	for(register int i = head[u]; ~i; i = e[i].next) {
		int v = e[i].v;
		if(v == fa || vis[v]) continue;
		getroot(v, u, tot, root);
		h[u] = max(h[u], son[v]);
		son[u] += son[v];
	}
	h[u] = max(tot - son[u], h[u]);
	if(h[u] < h[root]) root = u;
}
void init() {
	son[1] = n, h[0] = 0x3f3f3f3f, root[1] = 1;
	memset(vis, 0, sizeof(vis));
}
void getdepth(int u, int fa) {
	d[dcnt++] = depth[u];
	for(register int i = head[u]; ~i; i = e[i].next) {
		int v = e[i].v;
		if(v == fa || vis[v]) continue;
		depth[v] = depth[u] + e[i].w;
		getdepth(v, u); 
	}
}
int calc(int u, int ini) {
	dcnt = 0, depth[u] = ini;
	int ans = 0;
	getdepth(u, 0);
	sort(d, d + dcnt);
	for(register int l = 0, r = dcnt - 1; l < r;) 
		if(d[l] + d[r] <= k) ans += r - l, ++l;
		else --r;
	return ans;
}
int dfs(int u) {
	ans += calc(u, 0), vis[u] = 1;
	for(register int i = head[u]; ~i; i = e[i].next) {
		int v = e[i].v;
		if(vis[v]) continue;
		ans -= calc(v, e[i].w), root[v] = 0;
		getroot(v, 0, son[v], root[v]);
		dfs(root[v]);
	}
}
int main() {
	while(1) {
		scanf("%d%d", &n, &k);
		if(n == 0 && k == 0) return 0;
		cnt = 0, ans = 0;
		memset(head, -1, sizeof(head));
		for(register int i = 1; i < n; ++i) {
			int u, v, w;
			scanf("%d%d%d", &u, &v, &w);
			adde(u, v, w);
			adde(v, u, w);
		}
		init();
		dfs(1);
		printf("%d\n", ans);
	}
}