Tree

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 25286		Accepted: 8421

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. 

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. 

For each test case output the answer on a single line.

5 4

1 2 3

1 3 1

1 4 2

3 5 1

0 0

8

点分治通常用以解决树上的分治问题，以点为界分治。【我做题还不够多，先不详细讲，之后再总结

这道题要求所有d(u,v) <= k的对数，直接枚举肯定不行，我们先求出路径经过树上一点的路径数

如何求通过一点的路径数？

我们以该点为根并求出树中所有点到根的距离，再全部排序，用双指针的方法O(n)统计d[u] + d[v] <= k的对数ans1

但是会将都在同一个子树，也就是不经过根的路径也算上，再对每一个子树算一遍ans2减去就好了

就是ans1 - ∑ans2

之后再向下分治，向每颗子树递归。

为防止极端数据，我们每次求出重心为根

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)

using namespace std;

const int maxn = 10005,maxm = 40005,INF = 1000000000;

inline int RD(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}

	return out * flag;

}

int N,K,vis[maxn],head[maxn],d[maxn],dep[maxn],nedge = 0,F[maxn],Siz[maxn],rt = 0,n,ans;

struct EDGE{int to,w,next;}edge[maxm];

inline void build(int u,int v,int w){

	edge[nedge] = (EDGE){v,w,head[u]}; head[u] = nedge++;

	edge[nedge] = (EDGE){u,w,head[v]}; head[v] = nedge++;

}

void getRT(int u,int fa){

	int to; F[u] = 0; Siz[u] = 1;

	Redge(u) if ((to = edge[k].to) != fa && !vis[to]){

		getRT(to,u);

		Siz[u] += Siz[to];

		F[u] = max(F[u],Siz[to]);

	}

	F[u] = max(F[u],n - Siz[u]);

	if (F[u] < F[rt]) rt = u;

}

void getdep(int u,int fa){

	dep[++dep[0]] = d[u]; int to;

	Redge(u) if (!vis[to = edge[k].to] && to != fa){

		d[to] = d[u] + edge[k].w;

		getdep(to,u);

	}

}

int cal(int u,int D){

	d[u] = D; dep[0] = 0;

	getdep(u,0);

	sort(dep + 1,dep + 1 + dep[0]);

	int l = 1,r = dep[0],t = 0;

	while (l < r)

		if (dep[l] + dep[r] <= K) t += r - l++;

		else r--;

	return t;

}

void solve(int u){

	ans += cal(u,0);

	vis[u] = true; int to;

	Redge(u) if (!vis[to = edge[k].to]){

		ans -= cal(to,edge[k].w);

		n = Siz[to]; rt = 0;

		getRT(to,rt);

		solve(rt);

	}

}

int main(){

	while (true){

		memset(head,-1,sizeof(head));

		memset(vis,0,sizeof(vis));

		int a,b,w; N = RD(); K = RD(); ans = 0; rt = 0; nedge = 0;

		if (!N) break;

		REP(i,N - 1){

			a = RD(); b = RD(); w = RD();

			build(a,b,w);

		}

		n = N; F[0] = INF;

		getRT(1,0);

		solve(rt);

		printf("%d\n",ans);

	}

	return 0;

}