记录编号	365192	评测结果	AAAAAAAAAA
题目名称	[POJ1741][男人八题]树上的点对	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	0.711 s
提交时间	2017-01-19 21:18:05	内存使用	1.36 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 10005;
struct Edge {
	int next, to, dis;
	Edge(int a=0, int b=0, int c=0):
		next(a), to(b), dis(c) {}
} e[maxn*6];
int head[maxn<<1], tot = 1, rhead[maxn<<1];
void Add(int u, int v, int w, int *head) {
	e[++tot] = Edge(head[u], v, w); head[u] = tot;
}
void bAdd(int u, int v, int w, int *head) {
	Add(u, v, w, head); Add(v, u, w, head);
}
int N, K, pt, size[maxn<<1], ans;
int F, Size, mide;
bool vis[maxn*6];
int d1[maxn], d2[maxn];

void rebuild(int,int);
void getdep(int x, int fa, int dis, int *d) {
	if(x<=N) d[++d[0]] = dis;
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[i] || to==fa) continue;
		getdep(to, x, dis+e[i].dis, d);
	}
}
void calc(int m) {
	int u = e[m].to, v = e[m^1].to;
	d1[0] = d2[0] = 0;
	getdep(u, -1, 0, d1);
	getdep(v, -1, 0, d2);
	sort(d1+1, d1+d1[0]+1);
	sort(d2+1, d2+d2[0]+1);
	// for(int i=1; i<=d1[0]; ++i) printf("%d ", d1[i]); puts("");
	// for(int i=1; i<=d2[0]; ++i) printf("%d ", d2[i]); puts("");
	int l = 1, r = d2[0];
	while(l<=d1[0] && r) {
		while(r && d1[l]+e[m].dis+d2[r]>K) --r;
		ans += r;
		++l;
	}
}
int getmide(int x, int fa) {
	size[x] = 1;
	for(int i=head[x]; i; i=e[i].next) {
		int to = e[i].to;
		if(vis[i] || to==fa) continue;
		size[x] += getmide(to, x);
		int f = max(size[to], Size-size[to]);
		if(f<=F) F = f, mide = i;
	}
	return size[x];
}
void solve(int m) {
	int u = e[m].to, v = e[m^1].to;
	vis[m] = vis[m^1] = 1;
	calc(m); 
	// printf("solve %d %d %d\n", u, v, ans);
	F = Size = size[u]; getmide(u, -1); 
	if(size[u]>1) solve(mide);
	F = Size = size[v]; getmide(v, -1); 
	if(size[v]>1) solve(mide);
}
int main() {
	freopen("poj1741_tree.in","r",stdin);
	freopen("poj1741_tree.out","w",stdout);
	while(scanf("%d%d", &N, &K)!=EOF && N ) {
		memset(head, 0, sizeof head); tot = 1;
		memset(rhead, 0, sizeof rhead);
		memset(vis, 0, sizeof vis);

		for(int i=1,a,b,c; i<N; ++i) {
			scanf("%d%d%d", &a, &b, &c);
			bAdd(a, b, c, head); 
		}
		pt = N, rebuild(1, -1);
		memcpy(head, rhead, sizeof head);
		// for(int i=1; i<=pt; ++i) 
		// 	for(int j=head[i]; j; j=e[j].next)
		// 		printf("%d %d %d\n", i, e[j].to, e[j].dis);
		ans = 0; //warn
		F = Size = pt, getmide(1, 0); 
		solve(mide);
		printf("%d\n", ans);
	}
	return 0;
}

queue<pair<int,int> > q;
void rebuild(int x, int fa) {
	for(int i=head[x]; i; i=e[i].next) 
		if(e[i].to!=fa) rebuild(e[i].to, x);
	for(int i=head[x]; i; i=e[i].next) 
		if(e[i].to!=fa) q.push(make_pair(e[i].to, e[i].dis));
	int cnt = q.size();
	pair<int,int> a, b;
	while(cnt>2) {
		a = q.front(); q.pop();
		b = q.front(); q.pop();
		++pt;
		bAdd(pt, a.first, a.second, rhead);
		bAdd(pt, b.first, b.second, rhead);
		q.push(make_pair(pt, 0));
		--cnt;
	}
	while(!q.empty()) {
		bAdd(x, q.front().first, q.front().second, rhead);
		q.pop();
	}
}