N（n<=40000） 接下来n-1行边描述管道，按照题目中写的输入 接下来是k

一行，有多少对点之间的距离小于等于k

71 6 136 3 93 5 74 1 32 4 204 7 210

5

#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <stack>#include <vector>#include <queue>#include <cstring>#include <string>#include <map>#include <set>using namespace std;const int BufferSize = 1 << 16;char buffer[BufferSize], *Head, *Tail;inline char Getchar() {    if(Head == Tail) {        int l = fread(buffer, 1, BufferSize, stdin);        Tail = (Head = buffer) + l;    }    return *Head++;}int read() {    int x = 0, f = 1; char c = getchar();    while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); }    while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); }    return x * f;}#define maxn 40010#define maxm 80010int n, m, K, head[maxn], next[maxm], to[maxm], dist[maxm], ans;void AddEdge(int a, int b, int c) {	to[++m] = b; dist[m] = c; next[m] = head[a]; head[a] = m;	swap(a, b);	to[++m] = b; dist[m] = c; next[m] = head[a]; head[a] = m;	return ;}bool vis[maxn];int root, size, f[maxn], siz[maxn];void getroot(int u, int fa) {	siz[u] = 1; f[u] = 0;	for(int e = head[u]; e; e = next[e]) if(!vis[to[e]] && to[e] != fa) {		getroot(to[e], u);		siz[u] += siz[to[e]];		f[u] = max(f[u], siz[to[e]]);	}	f[u] = max(f[u], size - siz[u]);	if(f[root] > f[u]) root = u;	return ;}int A[maxn], tot, B[maxn], ToT;void dfs(int u, int fa, int d) {	if(d > K) return ;	A[++tot] = d;	for(int e = head[u]; e; e = next[e]) if(!vis[to[e]] && to[e] != fa)		dfs(to[e], u, d + dist[e]);	return ;}void solve(int u) {//	printf("u: %d\n", u);	vis[u] = 1;	ToT = 0;	int sum = 0;	for(int e = head[u]; e; e = next[e]) if(!vis[to[e]]) {		tot = 0;		dfs(to[e], u, dist[e]);		sort(A + 1, A + tot + 1);		ans += tot;//		for(int i = 1; i <= tot; i++) printf("%d ", A[i]); putchar(‘\n‘);		for(int i = 1; i <= tot; i++) {			int k = upper_bound(A + 1, A + tot + 1, K - A[i]) - A - 1;			sum += k;//			printf("%d ", k);		}//		puts("end");		for(int i = 1; i <= tot; i++) B[++ToT] = A[i];	}//	printf("here: %d ", sum);	int tmp = 0;	sort(B + 1, B + ToT + 1);	for(int i = 1; i <= ToT; i++) {		int k = upper_bound(B + 1, B + ToT + 1, K - B[i]) - B - 1;		tmp += k;	}//	printf("%d\n", tmp);	ans += (tmp - sum >> 1);	for(int e = head[u]; e; e = next[e]) if(!vis[to[e]]) {		root = 0; f[0] = n + 1; size = siz[u]; getroot(to[e], u);		solve(root);	}	return ;}int main() {	n = read();	for(int i = 1; i < n; i++) {		int a = read(), b = read(), c = read();		AddEdge(a, b, c);	}	K = read();		root = 0; f[0] = n + 1; size = n; getroot(1, 0);	solve(root);		printf("%d\n", ans);		return 0;}