Description
奶牛们从世界各地聚集起来参加一场大型聚会。总共有N头奶牛，N?1对奶牛互为朋友。每头奶牛都可以通过一些朋
友关系认识其他每头奶牛。她们玩得很开心，但是现在到了她们应当离开的时间了，她们会一个接一个地离开。她
们想要以某种顺序离开，使得只要至少还有两头奶牛尚未离开，所有尚未离开的奶牛都还有没有离开的朋友。此外
，由于行李寄存的因素，有M对奶牛(ai,bi)必须满足奶牛ai要比奶牛bi先离开。注意奶牛ai和奶牛bi可能是朋友，
也可能不是朋友。帮助奶牛们求出，对于每一头奶牛，她是否可以成为最后一头离开的奶牛。可能会发生不存在满 足上述要求的奶牛离开顺序的情况。
Input
输入的第1行包含两个空格分隔的整数N和M。
输入的第2≤i≤N行，每行包含两个整数xi和yi，满足1≤xi,yi≤N，xi≠yi，表示奶牛xi和奶牛yi是朋友关系。
输入的第N+1≤i≤N+M行，每行包含两个整数ai和bi，满足1≤ai,bi≤N，ai≠bi，表示奶牛ai必须比奶牛bi先离开聚会。
输入保证1≤N,M≤10^5
Output
输出N行，每行包含一个整数di，如果奶牛i可以成为最后一头离开的奶牛，则di=1，否则di=0
Sample Input
5 1
1 2
2 3
3 4
4 5
2 4
Sample Output
0
0
1
1
1
题解
我的做法凉凉噜…
然后tkj告诉了我一个重要的结论，就是合法的点一定是一个连通块
然后就会做了
我们首先先可以注意到，每次删掉的一定是叶子节点
那么什么情况下一个点不合法呢
不妨设有向边x->y表示x必须在y之前走
那么以某个点为根，不存在任意一个父亲通过上面有向边的DAG走能到达自己的子树里的点的
这个点就是合法的
那我的做法就是考虑每条边的贡献，每次让一些边凉掉
但是这样需要知道DAG中x能走到的点与某一个连续范围的点的交集
然后就凉了…
但是有了上面那个结论的话，我们可以暴力找出第一个合法点
具体怎么找就每次删去一个没有限制的叶子节点
最后留下来一个点就是了…否则你找不到其他合法点的
那么再考虑另外怎么样，画图模拟可知只要这个点没有出边那么就是合法的
于是就没有了…
有没有能告诉我我的做法怎么做的呀麻烦评论一下吧qwq哦我的做法是真的…
就你发现，x能走到的点一定只在他一棵子树里面
否则的话，x在任何一个合法的时间删掉都会造成出现两个连通块
那么你只需要记录一下dfs序的min和max，DAG反向转移就行了
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';ch=getchar();}return x*f;
}
int stack[20];
inline void write(LL x)
{
if(x<0){
putchar('-');x=-x;}if(!x){
putchar('0');return;}int top=0;while(x)stack[++top]=x%10,x/=10;while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){
write(x);putchar(' ');}
inline void pr2(LL x){
write(x);putchar('\n');}
const int MAXN=1000005;
struct edge{
int x,y,next;}a[2*MAXN];int len,last[MAXN];
void ins(int x,int y){
len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;}bool ok[MAXN];
int ot[MAXN],in[MAXN];
vector<int> vec[MAXN];void dfs(int x,int fa)
{
if(ot[x])return ;ok[x]=true;for(int k=last[x];k;k=a[k].next){
int y=a[k].y;if(y!=fa)dfs(y,x);}
}
int n,m,du[MAXN];
queue<int> li;
int main()
{
n=read();m=read();for(int i=1;i<n;i++){
int x=read(),y=read();ins(x,y);ins(y,x);du[x]++;du[y]++;}for(int i=1;i<=m;i++){
int x=read(),y=read();vec[x].push_back(y);ot[x]++;in[y]++;}int cnt=n;for(int i=1;i<=n;i++)if(!in[i]&&du[i]==1)li.push(i);int o;while(!li.empty()){
int x=li.front();li.pop();cnt--;o=x;for(int i=0;i<vec[x].size();i++){
int y=vec[x][i];in[y]--;if(du[y]==1&&in[y]==0)li.push(y);}for(int k=last[x];k;k=a[k].next){
du[a[k].y]--;if(du[a[k].y]==1&&in[a[k].y]==0)li.push(a[k].y);}}if(cnt!=0){
for(int i=1;i<=n;i++)pr2(0);return 0;}dfs(o,0);for(int i=1;i<=n;i++)pr2(ok[i]);return 0;
}