自动搬运

查看原文

来自洛谷，原作者为

	Bartholomew **

搬运于2025-08-24 22:07:44，当前版本为作者最后更新于2019-02-02 20:23:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简化题意

简化为给定一棵大小为$n$的树, 有$m$个限制

• 限制$(u,v)$ 表示$u$必须在$v$前删除

问每次删除一个叶子节点, 可能最后留下的点的集合

分析

nice problem

不难发现: 如果没有限制, 那么所有的点都可行...

首先, 我们可以贪心先找出一个可行点, 解决方法如下

每次寻找一个没有限制条件的叶子节点删去 重复上述操作, 最后的节点即为可行答案之一 若不成功, 则视为无解

Prove

• 如果本身数据无解, 那么自然上述方法找不到一个合法的删点序列

• 同样的, 如果不存在一个合法的删点序列, 那么必定意味着存在一个连续的子树: 子树中的任意一个点都被其他点的约束限制着, 类似于形成了环. 那么就不会存在任意一个序列可以打破这种局面了.

于是证明了该方法是可以找出合法点以及判断无解的!

sol

先提供一个$O(n^2)$的做法:

• 每次判断一个点是否可行, 只要将它提为root,并将所有边记为子节点指向父节点
• 若不存在环便是可行点, 否则非法!

那么会发现一个trick:

• 若存在限制$(u,v)$那么以$v$为根的$u$的子树(包括$u$)都不可行

这样就可以搞事情了

我们既然已经找出了一个可行解(记为$rt$)

• 以$rt$为根可以发现任意一个限制(a,b)中, a的子树一定是不可行的(证明略)

• 那么标记完不可行点之后剩下的点都是可行的!

  Prove 利用数学归纳: 只要证明与一个可行点相邻的且未被标记过的点同样合法即可!

  设该可行点为$s$, 转为root, 那么$t$为其子节点 如果关于$s$的合法删除序列为$\{a_n\}$ s.t. $a_n=s,a_x=t$ ($x\in Z$) 那么我们直接将$a_x$提至序列的$a_n$之后, 该序列同样合法

因为没有$t$必须在某一点前删除的限制, 否则$t$已经在之前被标记为非法!

且t的子树可以按序删除(不然$s$不会为合法点),以及$s$的非t子树部分同样可以删除,依旧不会被$t$所干扰

那么可以发现所有的可行解必定都是一起的, 一遍dfs即可...

复杂度: O(n)

Code

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

namespace {
	template <typename T> inline void read(T &x) {
		x = 0; T f = 1; char c = getchar();
		for(; !isdigit(c); c = getchar())
			if(c == '-') f = -1;
		for(;  isdigit(c); c = getchar())
			x = (x << 3) + (x << 1) + (c ^ 48);
		x *= f;
	}
}

const int N = 1E5 + 50;

int n, m, rt, d[N], vis[N], ans[N];
vector<int> g[N], l[N];
queue<int> que;

int cnt;
int solve(int cnt = 0) {
	for(; !que.empty(); ) {
		int u = que.front(); que.pop();
		++ cnt;
		if(d[u] != 1) {
			if(d[u] < 1) return u;
			for(int i = 1; i <= n; ++i) printf("0\n");
			exit(0);
		} 
		for(auto v : g[u]) {
			-- d[v]; ++ cnt;
			if(d[v] == 1) que.push(v);
		}
		for(auto v : l[u]) {
			-- d[v]; ++ cnt;
			if(d[v] == 1) que.push(v);
		}
	}
	if(cnt != n) {
		for(int i = 1; i <= n; ++i) printf("0\n"); 
		exit(0);
	}
}
void dfs(int u, int fa = -1) {
	ans[u] = 1;
	for(auto v : g[u]) 
		if(v != fa && !vis[v]) 
			dfs(v, u);
}
int main() {
	read(n), read(m);
	for(int u, v, i = 1; i < n; ++i) {
		read(u), read(v);
		g[u].push_back(v), g[v].push_back(u); 
		++ d[u], ++ d[v];
	}
	for(int a, b, i = 1; i <= m; ++i) {
		read(a), read(b);
		l[a].push_back(b);
		++ d[b];
		vis[a] = true;
	}
	for(int i = 1; i <= n; ++i) 
		if(d[i] == 1) que.push(i);
	rt = solve();
	dfs(rt);
	for(int i = 1; i <= n; ++i)
		printf("%d\n", ans[i]);
	return 0;
}