首先,这题要对题意先进行一个转化。
可以发现,这是一棵树,并且,我们要删点,肯定要从叶子节点开始删,才能保证在大于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; }View Code