题面

题解

删一条边、加一条边，相当于把一个子树折下来，然后嫁接在一个点上，

那么最优的情况肯定是接在根上，对吧，很好理解吧

那么这个拆下来的子树大小就不能超过n/2。

我们用son[]来表示每个点为根的子树大小，

如果一个点x可以改造后变成重心，那么要么它本来就是重心，要么它最多只有一个儿子y的son[y]大于n/2，并且y的子树大小可以通过改造变得<=n/2。

要改造一个儿子的子树，最优的方法就是减去里面最大的小于等于n/2的子子树，我们用dp1[]来表示一个点的子树里这样一个子子树的大小，然后暴力判就是了。

由于每个点的父亲也要考虑，所以用换根DP，一个dp2[]表示对于除了点的子树以外的部分可以剪掉的最大的部分。

转移方程：

dp1[x] = max{son[y]*2 <= n ? son[y] : dp1[y]}  //y 为 x 的儿子

dp2[x] = (n - son[x])*2 <= n ? (n - son[x]) : max(dp2[father[x]],max{son[y]*2 <= n ? son[y] : dp1[y]})  //y 为 x 的父亲除了 x 以外的其他儿子

/*

这里的dp2[x]后面不能暴力枚举y，只能处理出前缀最大值和后缀最大值来算

*/

注意，只能改造一次。

ＣＯＤＥ

zxy A了！ orz or2 orz

#include<cstdio>

#include<cstring>

#include<iostream>

//-----------F1

using namespace std;

#include<algorithm>

#include<cmath>

//-----------F2

#include<vector>

#include<stack>

#include<queue>

#include<map>

#define MAXN 400005

#define LL long long

#define lowbit(x) (-(x) & (x))

#define ENDL putchar('\n')

//#pragma GCC optimize(2)

//#pragma G++ optimize(3)

//#define int LL

char char_read_before = 1;

inline int read() {

	int f = 1,x = 0;char s = char_read_before;

	while(s < '0' || s > '9') {if(s == '-') f = -1;s = getchar();}

	while(s >= '0' && s <= '9') {x = x * 10 - '0' + s;s = getchar();}

	char_read_before = s;return x * f;

}

LL zxy = 1000000007ll; // 用来膜的

inline LL qkpow(LL a,LL b) {

	LL res = 1;

	while(b>0) {

		if(b & 1) res = res * a % zxy;

		a = a * a % zxy;

		b >>= 1;

	}

	return res;

}

int n,m,i,j,s,o,k;

struct it{

	int v,w;

	it(){v=w=0;}

	it(int V,int W){v = V;w = W;}

};

vector<int> g[MAXN];

vector<int> pre[MAXN],suf[MAXN];

int son[MAXN];

int dp1[MAXN],dp2[MAXN];

int ans[MAXN];

inline void dfs1(int x,int fa) {

	dp1[x] = 0;

	int sum = 0;

	pre[x].push_back(0);

	son[x] = 1;

	stack<int> sf;

	for(int i = 0;i < g[x].size();i ++) {

		if(g[x][i] != fa) {

			dfs1(g[x][i],x);

			son[x] += son[g[x][i]];

			dp1[x] = max(dp1[x],son[g[x][i]]*2 <= n ? son[g[x][i]] : dp1[g[x][i]]);

			sum = max(sum,son[g[x][i]]*2 <= n ? son[g[x][i]] : dp1[g[x][i]]);

		}

		pre[x].push_back(sum);

	}

	sum = 0;

	sf.push(0);

	for(int i = (int)g[x].size() - 1;i >= 0;i --) {

		if(g[x][i] != fa) {

			sum = max(sum,son[g[x][i]]*2 <= n ? son[g[x][i]] : dp1[g[x][i]]);

		}

		sf.push(sum);

	}

	while(!sf.empty()) suf[x].push_back(sf.top()),sf.pop();

	return ;

}

inline void dfs2(int x,int fa,int ll,int rr) {

	ans[x] = 1;

	int ct = 1;

	if(fa) {

		dp2[x] = (n - son[x])*2 <= n ? (n - son[x]) : max(dp2[fa],max(pre[fa][ll],suf[fa][rr]));

		if((n - son[x])*2 > n) {

			if((n - son[x] - dp2[x])*2 > n) ans[x] = 0;

			ct = 0;

		}

	}

	else dp2[x] = 0;

	for(int i = 0;i < g[x].size();i ++) {

		if(g[x][i] != fa) {

			dfs2(g[x][i],x,i,i+1);

			if(son[g[x][i]]*2 > n) {

				if(ct == 0 || (son[g[x][i]] - dp1[g[x][i]])*2 > n) ans[x] = 0;

				ct = 0;

			}

		}

	}

	return ;

}

signed main() {

	n = read();

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

		s = read();o = read();

		g[s].push_back(o);

		g[o].push_back(s);

	}

	dfs1(1,0);

	dfs2(1,0,0,0);

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

		printf("%d ",ans[i]);

	}

	return 0;

}

巴特西

Centroids （换根DP）

题面

题解

ＣＯＤＥ

最新文章

热门文章