백준 BOJ 14458 - [USACO Platinum] Cow at Large (Platinum)

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_BOOKNU
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// ........................macro.......................... //
#define FOR(i, f, n) for(int (i) = (f); (i) < (int)(n); ++(i))
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (int)(n); --(i))
#define pb push_back
#define emb emplace_back
#define fi first
#define se second
#define ENDL '\n'
#define sz(A) (int)(A).size()
#define ALL(A) A.begin(), A.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define next next9876
#define prev prev1234
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef long long i64;
typedef unsigned long long ui64;
// inline i64 GCD(i64 a, i64 b) { if(b == 0) return a; return GCD(b, a % b); }
inline int getidx(const vi& ar, int x) { return lower_bound(ALL(ar), x) - ar.begin(); } // 좌표 압축에 사용: 정렬된 ar에서 x의 idx를 찾음
inline i64 GCD(i64 a, i64 b) { i64 n; if(a < b) swap(a, b); while(b != 0) { n = a % b; a = b; b = n; } return a; }
inline i64 LCM(i64 a, i64 b) { if(a == 0 || b == 0) return GCD(a, b); return a / GCD(a, b) * b; }
inline i64 CEIL(i64 n, i64 d) { return n / d + (i64)(n % d != 0); } // 음수일 때 이상하게 작동할 수 있음.
inline i64 ROUND(i64 n, i64 d) { return n / d + (i64)((n % d) * 2 >= d); }
const i64 MOD = 1e9+7;
inline i64 POW(i64 a, i64 n) {
	assert(0 <= n);
	i64 ret;
	for(ret = 1; n; a = a*a%MOD, n /= 2) { if(n%2) ret = ret*a%MOD; }
	return ret;
}
template <class T> ostream& operator<<(ostream& os, vector<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class T> ostream& operator<<(ostream& os, set<T> v) {
	os << "[";
	int cnt = 0;
	for(auto vv : v) { os << vv; if(++cnt < v.size()) os << ","; }
	return os << "]";
}
template <class L, class R> ostream& operator<<(ostream& os, pair<L, R> p) { return os << "(" << p.fi << "," << p.se << ")"; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H, debug_out(T...); }
// ....................................................... //

struct fenwick {
	int n;
	vi t;
	void init(int _n) {
		n = _n;
		t.assign(n+1, 0);
	}
	void add(int u, int x) {
		for(++u; u <= n; u += (u&-u)) t[u] += x;
	}
	int sum(int u) {
		int ret = 0;
		for(++u; u > 0; u -= (u&-u)) ret += t[u];
		return ret;
	}
};

const int RN = 265, MAXN = RN*RN;
// dr, dl : 현재 정점부터 root까지, 최단 leaf까지 거리
// sn, en : inorder 순으로 정점에 번호를 부여할 때, u의 subtree의 번호 범위
// lza : 모든 노드에 더해진 dif, lz[b] : b번째 블럭 전체에 더해진 dif, dif[u] : u정점 자체에 더해진 dif
int n, dr[MAXN], dl[MAXN], deg[MAXN], ans[MAXN], sn[MAXN], en[MAXN], lza, lz[RN], dif[MAXN];
vi g[MAXN];
// dif : 0의 기준을 MAXN으로 사용한다.
// idx = dif, val = w = 2-deg(u)
fenwick ft[RN];
void input() {
	cin >> n;
	FOR(i, 1, n) {
		int u, v; cin >> u >> v; --u, --v;
		g[u].pb(v);
		g[v].pb(u);
	}
}

// dr, dl 계산
void disDfs(int u, int d, int p) {
	dr[u] = d;
	if(g[u].size() == 1) dl[u] = 0;
	else dl[u] = 0x7fffffff;
	for(int v : g[u]) {
		if(v == p) continue;
		disDfs(v, d+1, u);
		dl[u] = min(dl[u], dl[v] + 1);
	}
}

// dl[u] : u의 부모로부터 오는 leaf도 생각
void disDfs2(int u, int p) {
	if(p != -1) dl[u] = min(dl[u], dl[p] + 1);
	for(int v : g[u]) {
		if(v == p) continue;
		disDfs2(v, u);
	}
}

// sn, en 계산
int inorder(int u, int c, int p) {
	sn[u] = c;
	for(int v : g[u]) {
		if(v == p) continue;
		c = inorder(v, c+1, u);
	}
	return en[u] = c;
}

// 블럭 b에서 일부 [s, e] 정점들의 dif에 x를 더해준다.
// s, e는 inorder에 의해 부여된 정점 번호들이다.
void updateBlock(int b, int s, int e, int x) {
	FOR(i, s, e+1) ft[b].add(dif[i], -deg[i]);
	FOR(i, s, e+1) ft[b].add(dif[i] += x, deg[i]);
}

// u의 subtree의 dif에 전부 x를 더한다.
void updateSubtree(int u, int x) {
	int sb = sn[u]/RN, eb = en[u]/RN;
	// 한 블럭안에 다 들어가는 경우 따로 처리
	if(sb == eb) {
		updateBlock(sb, sn[u], en[u], x);
		return;
	}
	// 첫, 끝 블록은 쪼개어지기 때문에 따로 직접 처리한다.
	updateBlock(sb, sn[u], (sb+1)*RN-1, x);
	updateBlock(eb, eb*RN, en[u], x);
	// 중간 블록들은 블록 단위로 lazy를 적용한다.
	FOR(i, sb+1, eb) lz[i] += x;
}

// dfs로 답을 채워간다.
void getans(int u, int p) {
	// 현재 u를 기준으로 답을 구한다.
	// dif <= 0인 w들의 합 = subtree의 개수
	i64 res = 0;
	for(int i = 0; i < RN; ++i) {
		res += ft[i].sum(MAXN - lz[i] - lza); // 현재 dif + lz + lza인 값이 dif에 들어있으므로, MAXN - lz[i] - lza까지의 합을 구해야 0까지의 합을 구할 수 있음.
	}
	ans[u] = res;
	// 재귀
	for(int v : g[u]) {
		if(v == p) continue;
		// dif 조절 : subtree에는 ++dif, 그 외에는 --dif
		--lza;
		updateSubtree(v, 2);
		getans(v, u);
		// 복구
		++lza;
		updateSubtree(v, -2);
	}
}

int solve() {
	FOR(i, 0, RN) ft[i].init(2*MAXN);
	disDfs(0, 0, -1);
	disDfs2(0, -1);
	inorder(0, 0, -1);
	// 0-rooted일 경우 초기 계산.
	FOR(i, 0, n) {
		dif[sn[i]] = dl[i]-dr[i]+MAXN;
		deg[sn[i]] = 2-(int)g[i].size();
		ft[sn[i]/RN].add(dif[sn[i]], deg[sn[i]]);
	}
	getans(0, -1);
	FOR(i, 0, n) cout << (g[i].size() == 1 ? 1 : ans[i]) << ENDL;
	return 0;
}

// ................. main .................. //
void execute() {
	input(), solve();
}

int main(void) {
#ifdef LOCAL_BOOKNU
	freopen("input.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	cin.tie(0), ios_base::sync_with_stdio(false);
	execute();
	return 0;
}
// ......................................... //