Codeforces708C.Centroid

题目大意

一颗 \(n(2\leq n \leq 4\times10^5)\) 个节点的树，现在可以进行一次操作，将树上的一条边删去，之后加入一条新的边，操作完成后必须仍然是一棵树，判断对于每个节点，进行完操作后，其是否可能为树的重心（删去该点后剩余所有连通块的大小均 \(\leq \frac{n}{2}\) 。

思路

可以发现这个操作其实就是将树上的某一棵子树拆下来然后再拼到某一个地方，于是我们考虑树形 \(dp\) ，设 \(down[v]\) 为以 \(v\) 为根的向下的子树中大小不超过 \(\frac{n}{2}\) 的最大子树， \(up[v]\) 为以 \(v\) 为根的向上的子树中大小不超过 \(\frac{n}{2}\) 的最大子树， \(f[v]\) 为 \(v\) 的所有向下子树中最大子树的大小（以上都不包含以 \(v\) 为根的子树）。

之后我们进行转移，对于 \(v\) 的每个儿子 \(to\) ,因为至多有一个儿子的 \(size[to]>\frac{n}{2}\) ，并且以 \(to\) 为根的子树内最大的一个子树就是其本身，于是可以得到：

\[f[v]=max(f[v],size[to]) \]

\[down[v]=\left\{ \begin{array}{**lr**} max(down[v],size[to]), & size[to]\leq \frac{n}{2} \\ max(down[v],down[to]), & size[to]> \frac{n}{2} \\ \end{array} \right. \]

以上两个我们可以以任意节点为根在第一次 \(dfs\) 时得到。对于 \(up[v]\) ，在我们第二次 \(dfs\) 到节点 \(v\) 时，我们用 \(set\) 来维护其所有儿子 \(to\) 的 \(down[to]\) ，之后对于每一个 \(to\) ，与求 \(down[\space]\) 时类似，如果 \(n-size[to]\leq \frac{n}{2}\) ，那么 \(up[to]=max(up[to],n-size[to])\) ，否则我们可以先令 \(up[to]=max(up[to],up[v])\) ，将 \(v\) 先将向上子树的部分考虑进去，之后我们在 \(set\) 中删去 \(down[to]\) ，于是现在 \(set\) 中维护的就是 \(v\) 的不含 \(to\) 的所有儿子的 \(down[\space]\)，也就是 \(to\) 的向上子树尚未被考虑的部分，我们取出其中的最大值 \(mx\) ，于是再令 \(up[to]=max(up[to],mx)\) 即可得到 \(up[to]\) 。

我们考虑如何根据我们两次 \(dfs\) 所求来进行判断，如果 \(f[v]\leq \frac{n}{2}\) ，自然是可以的，否则，就必须找到节点 \(v\) 的最大的一棵子树，找出其中大小 \(\leq \frac{n}{2}\) 的最大的子树，我们可以将其拆下来作为 \(v\) 的新的一棵子树再装回去，于是只需要让原来最大子树剩下的部分大小 \(\leq \frac{n}{2}\) 即可，我们先判断最大子树是不是向上子树，如果是，那么判断 \(n-size[v]-up[v]\) 是否 \(\leq \frac{n}{2}\) 即可，如果不是，\(f[v]-down[v]\) 是否 \(\leq \frac{n}{2}\) 即可，时间复杂度 \(O(nlogn)\) 。

代码

#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
#define all(x) x.begin(),x.end()
//#define int LL
//#define lc p*2+1
//#define rc p*2+2
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL mod = 1000000007;
const LL MOD = 998244353;
const int maxn = 400010;

int N;
int f[maxn], vsize[maxn], down[maxn], up[maxn], lim;
bool ans[maxn];
vectorG[maxn];

void add_edge(int from, int to)
{
	G[from].push_back(to);
	G[to].push_back(from);
}

void dfs1(int v, int p)
{
	vsize[v] = 1;
	for (int i = 0; i < G[v].size(); i++)
	{
		int to = G[v][i];
		if (to == p)
			continue;
		dfs1(to, v);
		vsize[v] += vsize[to];
		f[v] = max(f[v], vsize[to]);
		down[v] = max(down[v], (vsize[to] > lim ? down[to] : vsize[to]));
	}
}

void dfs2(int v, int p)
{
	multisetS;
	for (int i = 0; i < G[v].size(); i++)
	{
		int to = G[v][i];
		if (to == p)
			continue;
		S.insert(vsize[to] > lim ? down[to] : vsize[to]);
	}
	for (int i = 0; i < G[v].size(); i++)
	{
		int to = G[v][i];
		if (to == p)
			continue;
		if (N - vsize[to] <= lim)
			up[to] = max(up[to], N - vsize[to]);
		else
		{
			up[to] = max(up[to], up[v]);
			S.erase(S.find(vsize[to] > lim ? down[to] : vsize[to]));
			if (!S.empty())
				up[to] = max(up[to], *S.rbegin());
			S.insert(vsize[to] > lim ? down[to] : vsize[to]);
		}
		dfs2(to, v);
	}
	if (N - vsize[v] > lim)
		ans[v] = N - vsize[v] - up[v] <= lim;
	else if (f[v] > lim)
		ans[v] = f[v] - down[v] <= lim;
	else
		ans[v] = true;
}

void solve()
{
	lim = N / 2;
	dfs1(1, 0);
	dfs2(1, 0);
	for (int i = 1; i <= N; i++)
		cout << (ans[i] ? 1 : 0) << ' ';
	cout << endl;
}

int main()
{
	IOS;
	cin >> N;
	int u, v;
	for (int i = 1; i < N; i++)
	{
		cin >> u >> v;
		add_edge(u, v);
	}
	solve();

	return 0;
}