首先，这题要对题意先进行一个转化。
可以发现，这是一棵树，并且，我们要删点，肯定要从叶子节点开始删，才能保证在大于2个点时。
每个点最少存在一个朋友。
那么，我们主要要去分析，当我们加入关系边时，有哪些点无法作为最后点了（如果没有关系边，那么从一个点两边删，肯定每条边都会满足）
从遥远的国度借鉴经验。
我们以1为根来考虑换根后的贡献变化。
当a不在1->b的链上时。那么只有a的子树无法，作为最后点。
因为a要比b先删，那么a的子树肯定要比a先删，就算不先删也肯定会断开了。
当a在1->b的链上时。除了a往b方向的子节点z的子树，其他的都无法作为最后点。（和上面差不多地思考一下就行）
所以，我们只需要判断位置，然后对于不合法的点进行加1，如果最后点的权值<=0，说明合法。
这里用dfs序差分来高效加值，因为dfs对于子树是连续的，所以可以直接差分，然后最后求一下前缀和即可。
这里，还需要思考一个问题：是否存在无解的情况。
事实上，我们可以发现，当存在环时，对于环上的点，即要比对方先删，又要对方比自己先删，肯定无法实现，那么相对的所有点都无法实现了。
所有，我们需要判断是否存在环。这里拓扑来判环。
注意的是，我们要对关系边，新建图，然后拓扑时同时去两张图拓扑。
然后我们在无向边时也要统计入度，然后对于叶子就是入度<2的点了（一开始是1，当后面可能<1）。
如果只对关系边统计如果，很可能不是叶子节点的点也入度 == 0，所以要这样统计
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef long double ld; typedef pair<LL,int> pii; const int N = 1e5+5; const int M = 2e6+5; const LL Mod = 998244353; #define rg register #define pi acos(-1) #define INF 1e18 #define INM INT_MIN #define dbg(ax) cout << "now this num is " << ax << endl; inline int read() { int x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } int n,m,in[N]; vector<int> G[N],vec[N]; int id[N],rk[N],dep[N],ssize[N],f[N][25],lg[N],c[N],vis[N],ans[N],tim = 0; void init() { for(int i = 1;i < N;++i) lg[i] = lg[i-1] + ((1<<lg[i-1]) == i); } void dfs(int u,int fa) { dep[u] = dep[fa]+1; f[u][0] = fa,ssize[u] = 1; id[u] = ++tim,rk[tim] = u; for(rg int i = 1;i <= lg[dep[u]];++i) f[u][i] = f[f[u][i-1]][i-1]; for(auto v : G[u]) { if(v == fa) continue; dfs(v,u); ssize[u] += ssize[v]; } } int LCA(int x,int y) { if(dep[x] < dep[y]) swap(x,y); while(dep[x] > dep[y]) { x = f[x][lg[dep[x]-dep[y]]-1]; } if(x == y) return x; for(rg int i = lg[dep[x]]-1;i >= 0;--i) if(f[x][i] != f[y][i]) x = f[x][i],y = f[y][i]; return f[x][0]; } int Get_fa(int x,int k) { for(int i = 24;i >= 0;--i) { if(k >= (1<<i)) x = f[x][i],k -= (1<<i); } return x; } bool slove() { 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(auto v : vec[u]) { in[v]--; if(in[v] < 2 && !vis[v]) { vis[v] = 1; Q.push(v); } } for(auto v : G[u]) { in[v]--; if(in[v] < 2 && !vis[v]) { vis[v] = 1; Q.push(v); } } } for(int i = 1;i <= n;++i) if(!vis[i]) return false; return true; } int main() { init(); n = read(),m = read(); for(int i = 1;i < n;++i) { int x,y;x = read(),y = read(); G[x].push_back(y); G[y].push_back(x); in[x]++,in[y]++; } dfs(1,0); while(m--) { int a,b;a = read(),b = read(); if(LCA(a,b) == a) { int xx = Get_fa(b,dep[b]-dep[a]-1); // dbg(xx); c[1]++,c[id[xx]]--; c[id[xx]+ssize[xx]]++,c[n+1]--; } else { c[id[a]]++,c[id[a]+ssize[a]]--; } vec[a].push_back(b); in[b]++; } if(!slove()) { for(int i = 1;i <= n;++i) printf("0\n"); } else { int sum = 0; for(int i = 1;i <= n;++i) { sum += c[i]; if(sum <= 0) ans[rk[i]] = 1; } for(int i = 1;i <= n;++i) printf("%d\n",ans[i]); } system("pause"); return 0; }