[USACO18DEC]The Cow Gathering

Description:

给定一棵树,每次删去叶子,有m个限制,分别为(a,b)表示a需要比b先删,为每个点能否成为最后被删的点

Hint:

\(n,m \le 10^5\)

Solution:

手模后会发现一个十分不显然的规律: 若a比b先删,则a在以b为根的子树中的点,都不能最后删,

于是这样就转化为这个题了:https://www.cnblogs.com/list1/p/10497877.html

每次直接打个差分标记

这题还要判无解的情况(这谁想得到啊)

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define ls p<<1

#define rs p<<1|1

using namespace std;

typedef long long ll;

const int mxn=5e5+5;

int n,m,cnt,tot,in[mxn],hd[mxn],vis[mxn],hd2[mxn],sz[mxn],dep[mxn],ans[mxn],tag[mxn],dfn[mxn],f[mxn][19];

inline int read() {

	char c=getchar(); int x=0,f=1;

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

	while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}

	return x*f;

}

inline int chkmax(int &x,int y) {if(x<y) x=y;}

inline int chkmin(int &x,int y) {if(x>y) x=y;}

struct ed {

	int to,nxt;

}t[mxn<<1];

inline void add(int u,int v) {

	t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;

}

inline void add2(int u,int v) {

    t[++cnt]=(ed) {v,hd2[u]}; hd2[u]=cnt;

    ++in[v];

}

int up(int u,int k)

{

	for(int i=30;i>=0;--i)

		if(k&(1<<i)) u=f[u][i];

	return u;

}

void dfs(int u,int fa)

{

	f[u][0]=fa; dfn[u]=++tot; dep[u]=dep[fa]+1; sz[u]=1;

	for(int i=hd[u];i;i=t[i].nxt) {

		int v=t[i].to;

		if(v==fa) continue ;

		dfs(v,u); sz[u]+=sz[v];

	}

}

void solve(int u,int fa,int val)

{

	val+=tag[u]; ans[u]=val>0;

	for(int i=hd[u];i;i=t[i].nxt) {

		int v=t[i].to;

		if(v==fa) continue ;

		solve(v,u,val);

	}

}

int flag=0;

void check()

{

	queue<int > q;

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

		if(in[i]<2) q.push(i),vis[i]=1;

		while(!q.empty()) {

			int u=q.front(); q.pop();

			for(int i=hd[u];i;i=t[i].nxt) {

				int v=t[i].to; --in[v];

				if(!vis[v]&&in[v]<2) {

					vis[v]=1;

					q.push(v);

				}

			}

			for(int i=hd2[u];i;i=t[i].nxt) {

				int v=t[i].to; --in[v];

				if(!vis[v]&&in[v]<2) {

					vis[v]=1;

					q.push(v);

				}

			}

		}

	for(int i=1;i<=n;++i) if(!vis[i]) flag=1;

}

int main()

{

	n=read(); m=read(); int u,v,w;

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

		u=read(); v=read();

		add(u,v); add(v,u);

		++in[u]; ++in[v];

	}

	dfs(1,1); f[1][0]=1;

	for(int j=1;j<=18;++j)

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

			f[i][j]=f[f[i][j-1]][j-1];

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

		u=read(); v=read(); add2(u,v);

		if(dfn[v]>dfn[u]&&dfn[v]<dfn[u]+sz[u]) {

			int pos=up(v,dep[v]-dep[u]-1);

			--tag[pos];

			++tag[1];

		}

		else ++tag[u];

	}

	check();

	if(flag) {

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

			printf("0\n");

		return 0;

	}

	solve(1,1,0);

	for(int i=1;i<=n;++i) printf("%d\n",ans[i]^1);

    return 0;

}