AIM Tech R3 div2 E Centroid

思路很明显了，假设是点x，则看它的子树中是否有大于n/2的，如果有，则在该子树中剪去它可以剪的且小于n/2的，接到点x上。

则统计出在以x点为根的子树中，它的各子树可以剪去的且小于n/2的最大子子树。对于除去以x为根的子树的其他部分，记为up，则同样地统计它的可以剪除的符合条件的子树，最后对每个点判断一下就可以了。

代码如下：：（额，想的时候对up的这个不知道怎么写~谢指导）

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <queue>

//#include <bitset>

using namespace std;

const int MAXN = 400010;

vector<int> t[MAXN];

int par[MAXN], sz[MAXN], up[MAXN], dw[MAXN], n;

void dfs_sz(int u, int parent){

	par[u] = parent;

	sz[u] = 1;

	int size = t[u].size();

	for(int i = 0; i< size; i++){

		int v = t[u][i];

		if(v == parent) continue;

		dfs_sz(v, u);

		sz[u] += sz[v];

	}

}

void dfs_down(int u, int parent){

	dw[u] = (sz[u] <= n/2 ? sz[u] : 0);

	int size = t[u].size();

	for(int i = 0; i < size; i++){

		int v = t[u][i];

		if(v == parent) continue;

		dfs_down(v, u);

		dw[u] = max(dw[u], dw[v]);

	}

}

void dfs_up(int u, int parent, int val){

	up[u] = max((n - sz[u] <= n /2? n - sz[u]: 0), val);

	int size = t[u].size();

	int mx0 = 0, mx1 = 0;

	for(int i = 0; i < size; i++){

		int v = t[u][i];

		if(v == parent) continue;

		if(dw[v] >= mx0){

			mx1 = mx0;

			mx0 = dw[v];

		}

		else if(dw[v] >= mx1){

			mx1 = dw[v];

		}

	}

	for(int i = 0; i < size ; i++){

		int v = t[u][i];

		if(v == parent) continue;

		dfs_up(v, u, max(up[u], (mx0 == dw[v]? mx1 : mx0 )));

	}

}

int main(){

	int u, v;

	scanf("%d", &n);

	for(int i = 1; i< n; i++){

		scanf("%d%d", &u, &v);

		t[u].push_back(v);

		t[v].push_back(u);

	}

	dfs_sz(1, -1);

	dfs_down(1, -1);

	dfs_up(1, -1, 0);

	for(int i = 1; i <= n; i++){

		int ans = 1;

		int size = t[i].size();

		for(int k = 0; k < size; k++){

			int u = t[i][k];

			if(u == par[i]){

				if(n - sz[i] - up[i] > n/2)

					ans = 0;

			}

			else {

				if(sz[u] - dw[u] > n/ 2)

					ans = 0;

			}

		}

		printf("%d", ans);

		if(i == n) printf("\n");

		else printf(" ");

	}

	return 0;

}