题解：P5157 The Cow Gathering P

怎么从看题到写完只用了不到 40min。是树太简单了还是什么。

简要题意

给一棵大小为 $n$ 的树，有 $m$ 个限制，限制 $(u,v)$ 表示删 $v$ 前必须删除 $u$。每次可以删除一个满足所有限制的叶子节点，问可能最后留下的点的集合。

思路

显然要先跑一遍拓排。先把树当作无根树，可以删除一个是叶子节点且不存在入度的节点。如果拓排遇到环了那全部输出 $0$。

然后对于一个节点 $r$，如果以 $r$ 为根节点时存在一个限制 $(u,v)$ 满足 $u$ 是 $v$ 的祖先那这个节点就是不行的。

随便让一个节点为根，不影响。考虑做树上差分，对于一个限制 $(u,v)$，存在两种情况：

• 如果此时 $u$ 是 $v$ 的祖先，那只有 $u$ 的子树（不包括 $u$）可以成为可行的点，因为对于这些点 $u$ 都会成为 $v$ 的祖先。
• 如果此时 $u$ 不是 $v$ 的祖先，那整个 $u$ 的子树（包括 $u$）都不是可行的点，因为相当于会把祖孙关系换过来。

然后还原差分数组，如果仍然被标记了 $>0$ 次那就无法成为答案。可以发现由于前面判过完全死掉的情况所以不会出现本来被标记过不可行的节点又被 $u \leftarrow u-1$ 的差分给叉掉的。

实现细节 & 代码

如果 $u$ 是 $v$ 的祖先那么 $u$ 肯定是最先进去，最晚出来的（相对于 $v$）。代码中使用了 in 和 out 数组完成。

注意代码中的 lca 求得不是最近公共祖先，而是 $v\to u$ 的路径上离 $u$ 最近的且不是 $u$ 的节点（说人话就是 $u$ 下面的那个节点）。

代码还是比较好想的。

#include<bits/stdc++.h>
#define For(a,b,c) for(int a=b;a<=c;a++)
#define Fro(a,b,c) for(int a=b;a>=c;a--)
#define pb push_back
using namespace std;
constexpr int N=1e5+5,MOD=998244353;
vector<int> g[N],ec[N];
int n,m,deg[N],ideg[N];
int up[N][20],dep[N],in[N],out[N],dfn,df[N];
bool vis[N];
int u_[N],v_[N];
void dfs1(int u,int p){
	in[u]=++dfn;
	up[u][0]=p;
	dep[u]=dep[p]+1;
	For(i,1,19)
		up[u][i]=up[up[u][i-1]][i-1];
	for(auto v:g[u]){
		if(v!=p)
			dfs1(v,u);
	}
	out[u]=dfn;
}
bool isanc(int u,int v){
	return in[u]<=in[v]&&out[u]>=out[v];
}
int lca(int u,int v){
	Fro(i,19,0)
		if(dep[v]-(1<<i)>dep[u])
			v=up[v][i];
	return v;
}
void dfs2(int u,int p){
	df[u]+=df[p];
	for(auto v:g[u]){
		if(v!=p)
			dfs2(v,u);
	}
}
int main(){
	cin>>n>>m;
	For(i,1,n-1){
		int u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
		deg[u]++;
		deg[v]++;
	}
	For(i,1,m){
		cin>>u_[i]>>v_[i];
		ec[u_[i]].pb(v_[i]);
		ideg[v_[i]]++;
	}
	queue<int> q;
	For(i,1,n)
		if(deg[i]<=1&&ideg[i]==0){
			q.push(i);
			vis[i]=1;
		}
	int cnt=0;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		cnt++;
		for(auto v:g[u]){
			deg[v]--;
			if(deg[v]<=1&&ideg[v]==0&&!vis[v]){
				q.push(v);
				vis[v]=1;
			}
		}
		for(auto v:ec[u]){
			ideg[v]--;
			if(deg[v]<=1&&ideg[v]==0&&!vis[v]){
				q.push(v);
				vis[v]=1;
			}
		}
	}
	if(cnt<n){
		For(i,1,n)
			cout<<0<<'\n';
		return 0;
	}
	dfs1(1,0);
	For(i,1,m){
		int u=u_[i],v=v_[i];
		if(isanc(u,v)){
			int w=lca(u,v);
			df[1]++;
			df[w]--;
		}
		else
			df[u]++;
	}
	dfs2(1,0);
	For(i,1,n){
		if(df[i]>0)
			cout<<0<<'\n';
		else
			cout<<1<<'\n';
	}
	return 0;
}