CF708C Centroids

题意

来自洛谷：

思路

记录每个点 \(u\) 所在子树可以删去的最大的部分 \(part1\) 和次大的部分 \(part2\) 和除了 \(u\) 的子树以外的部分可以删去的最大的部分 \(up\)，这些部分必须要求小于等于 \(\dfrac{n}{2}\)，和找树的中心（注意不是重心）的思路差不多。

注意：\(part1, part2\) 不能同时更新，\(up\) 的更新要注意点的取舍。

然后记录一下结点 \(u\) 子树最大的结点 \(maxch[u]\)。

对于每个点，如果他本来就是重心那它不用变。

否则其子树或者子树以外的部分必有大于 \(\dfrac{n}{2}\) 的部分。

子树大于 \(\dfrac{n}{2}\)，如果 \(sz[maxch[u]] - part1[maxch[u]] \le \dfrac{n}{2}\)，说明可以割掉这一部分再接到 \(u\) 上去，这样任何一个部分也不会超过 \(\dfrac{n}{2}\)。

对于子树之外的一部分超过 \(\dfrac{n}{2}\)，那就看如果 \((n - sz[u] - up[u]) \le \dfrac{n}{2}\)，那说明满足条件，和上面类似。

代码

细节挺多，本来想着口胡一下就过了算了。

// Problem: Centroids
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF708C
// Memory Limit: 500 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// up, part1, part2;

#include <bits/stdc++.h>

using namespace std;

const int N = 400010, M = 800010;

struct edge {
	int to, next;
} e[M];

int head[N], idx = 1;

void add(int u, int v) {
	idx++, e[idx].to = v, e[idx].next = head[u], head[u] = idx;
}

int n;
int sz[N];
int maxch[N], maxchr[N];
int part1[N], part2[N], up[N];          // part1: 最大的小于等于 n / 2 的子树，part2: 第二大的小于等于 n / 2 的子树
int chver[N];                           // 记录 part1 对应的结点
int f[N];
bool res[N];

bool updatepart(int u, int x, int c) {  // 更新 part1, part2
	if (x * 2 > n) return false;
	bool flag = false;
	if (part1[u] < x) {
		part2[u] = part1[u];
		part1[u] = x;
		chver[u] = c;
		flag = true;
	}
	else if (part2[u] < x) {
		part2[u] = x;
		flag = true;
	}
	return flag;
}

void dfs(int u, int fa) {               // dfs 记录子树大小，并找到 part1, part2 及 chver
	sz[u] = 1; f[u] = fa;
	for (int i = head[u]; i; i = e[i].next) {
		int to = e[i].to;
		if (to == fa) continue;
		dfs(to, u);
		sz[u] += sz[to];
		if (sz[to] > maxch[u]) {        // 记录 u 的最大子树
			maxch[u] = sz[to];
			maxchr[u] = to;
		}
		if (!updatepart(u, sz[to], to)) updatepart(u, part1[to], chver[to]);// 两者不能同时更新
	}
}

void dfsup(int u, int fa) {
	for (int i = head[u]; i; i = e[i].next) {       // 记录每个点除了这个子树的部分的 part1
		int to = e[i].to;
		if (to == fa) continue;
		up[to] = up[u];
		if ((n - sz[u]) * 2 <= n) up[to] = max(up[to], n - sz[u]);
		if (chver[u] == chver[to] || chver[u] == to) up[to] = max(up[to], part2[u]);
		else up[to] = max(up[to], part1[u]);
		dfsup(to, u);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v), add(v, u);
	}
	dfs(1, 0);
	dfsup(1, 0);	
			
	for (int u = 1; u <= n; u++) {
		int mxs = max(maxch[u], n - sz[u]);
		if (mxs * 2 <= n) {
			res[u] = true;
			continue;
		}
		if (maxch[u] * 2 > n) {                             // u 的子树的最大部分大于 n / 2
			if ((maxch[u] - part1[maxchr[u]]) * 2 <= n) {   // u 的子树的最大的部分减去能减去的最大部分
				res[u] = true;
			}
		}
		else {
			if ((n - sz[u] - up[u]) * 2 <= n) {             // u 的子树之外最大部分大于 n / 2
				res[u] = true;                              // u 的子树之外的部分减去能减去的最大部分
			}
		}
	}
	for (int i = 1; i <= n; i++) cout << res[i] << ' ';
	return 0;
}