USACO 2018 January Contest, Platinum Problem 2. Cow at Large JZOJ 100130. 鱼池逃脱（贪心+树上数数转换+点分治）

#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i <  _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

const int N = 70005;

int n, x, y, r[N];
int fi[N], to[N * 2], nt[N * 2], tot;

void link(int x, int y) {
	nt[++ tot] = fi[x], to[tot] = y, fi[x] = tot;
}

int d[N], d0, bz[N], f[N];

void bfs() {
	fo(i, 1, n) if(r[i] == 1)
		d[++ d0] = i, bz[i] = 1;
	for(int i = 1; i <= d0; i ++) {
		int x = d[i];
		for(int j = fi[x]; j; j = nt[j]) {
			int y = to[j];
			if(!bz[y]) bz[y] = 1, f[y] = f[x] + 1, d[++ d0] = y;
		}
	}
}

int siz[N], mx[N], G;

void fg(int x) {
	bz[x] = 1;
	siz[x] = 1; mx[x] = 0;
	for(int i = fi[x]; i; i = nt[i]) if(!bz[to[i]])
		fg(to[i]), siz[x] += siz[to[i]], mx[x] = max(mx[x], siz[to[i]]);
	mx[x] = max(mx[x], siz[0] - siz[x]);
	if(mx[x] < mx[G]) G = x;
	bz[x] = 0;
}

int dep[N];

void dfs(int x) {
	bz[x] = 1;
	d[++ d0] = x;
	for(int i = fi[x]; i; i = nt[i]) if(!bz[to[i]]) {
		dep[to[i]] = dep[x] + 1;
		dfs(to[i]);
	}
	bz[x] = 0;
}

ll cnt[N], ans[N];

void calc(int m, int xs) {
	fo(i, 0, m) cnt[i] = 0;
	fo(i, 1, d0) {
		int v = f[d[i]] - dep[d[i]];
		if(v <= m) cnt[max(0, v)] += 2 - r[d[i]];
	}
	fo(i, 1, m) cnt[i] += cnt[i - 1];
	fo(i, 1, d0) ans[d[i]] += xs * (cnt[dep[d[i]]]);
}

void dg(int x) {
	fg(x);
	d0 = 0; dep[x] = 0; dfs(x);
	calc(siz[x], 1);
	bz[x] = 1;
	for(int i = fi[x]; i; i = nt[i]) if(!bz[to[i]]) {
		int y = to[i];
		d0 = 0; dep[y] = 1; dfs(y);
		calc(siz[y], -1);
	}
	for(int i = fi[x]; i; i = nt[i]) if(!bz[to[i]])
		siz[0] = siz[to[i]], G = 0, fg(to[i]), dg(G);
}

int main() {
	freopen("atlarge.in", "r", stdin);
	freopen("atlarge.out", "w", stdout);
	scanf("%d", &n);
	if(n == 1) {
		pp("1\n"); return 0;
	}
	fo(i, 1, n - 1) {
		scanf("%d %d", &x, &y);
		link(x, y); link(y, x);
		r[x] ++; r[y] ++;
	}
	bfs();
	fo(i, 1, n) bz[i] = 0;
	siz[0] = mx[0] = n, fg(1), dg(G);
	fo(i, 1, n) pp("%lld\n", r[i] == 1 ? 1 : ans[i]);
}