洛谷P5157 [USACO18DEC]The Cow Gathering P 题解
题目链接：P5157 [USACO18DEC]The Cow Gathering P
题意：
奶牛们从世界各地聚集起来参加一场大型聚会。总共有 $ N $ 头奶牛， $ N-1 $ 对奶牛互为朋友。每头奶牛都可以通过一些朋友关系认识其他每头奶牛。
她们玩得很开心，但是现在到了她们应当离开的时间了，她们会一个接一个地离开。她们想要以某种顺序离开，使得只要至少还有两头奶牛尚未离开，所有尚未离开的奶牛都还有没有离开的朋友。此外，由于行李寄存的因素，有 $ M $ 对奶牛 $ (a_i,b_i) $ 必须满足奶牛 $ a_i $ 要比奶牛 $ b_i $ 先离开。注意奶牛 $ a_i $ 和奶牛 $ b_i $ 可能是朋友，也可能不是朋友。
帮助奶牛们求出，对于每一头奶牛，她是否可以成为最后一头离开的奶牛。可能会发生不存在满足上述要求的奶牛离开顺序的情况。
输入格式：
输入的第 $ 1 $ 行包含两个空格分隔的整数 $ N $ 和 $ M $ 。
输入的第 $ 2 \leq i \leq N $ 行，每行包含两个整数 $ x_i $ 和 $ y_i $ ，满足 $1 \leq x_i,y_i \leq N,~x_i \neq y_i$ ，表示奶牛 $ x_i $ 和奶牛 $ y_i $ 是朋友关系。
输入的第 $ N+1 \leq i \leq N+M $ 行，每行包含两个整数 $ a_i $ 和 $ b_i $ ，满足 $ 1 \leq a_i,b_i \leq N $ ， $ a_i \neq b_i $ ，表示奶牛 $ a_i $ 必须比奶牛 $ b_i $ 先离开聚会。
输出格式：
输出 $ N $ 行，每行包含一个整数 $ d_i $ ，如果奶牛 $ i $ 可以成为最后一头离开的奶牛，则 $ d_i=1 $ ，否则 $ d_i=0 $ 。
数据范围：
$1 \le N,M \le 10^5$ 。
注意到奶牛的朋友关系形成了无根树，而删除的过程其实就是在给它定向。
若 $i$ 是最后一个被删的，则该树可看作以 $i$ 为根的内向树 $T_i$ ，即“先”指向“后”。
当加入限制边后，若 $i$ 能成为最后一个删的，当且仅当 $T_i$ 和限制边的并是一个 DAG 。
但是我们不可能对每个节点都检查一遍，进而考察加入一条限制边 $(a_i,b_i)$ 后有什么影响。
我们钦定 $b_i$ 为无根树的新根，则此时 $a_i$ 所在子树的所有节点都不能作为内向树根节点（也就是被最后删除）。
则对于每条限制边，我们都标记出一个集合，然后取这些集合的并，就是不能最后删的节点。
但是剩下的节点一定可以删吗，答案是否定的，考虑下面这种情况：
不难发现这张图无解的原因就是定向后出现了环，那么怎么才能判断有没有出现环呢？
其实很简单，我们每次标记的集合所包含的边集，事实上都存在唯一的定向方式。
因此我们可以一边标记一边定向，定向过程中已经可以判断同一条边出现两种定向的无解情况了。
但是正如反例所示，仅仅这么做是不够的，因为我们还没有加入限制边。那么只需要最后跑一次判环就可以了。
再说下实现上的问题。如何快速找到「钦定 $b_i$ 为无根树的新根时 $a_i$ 所在子树的所有节点」呢？
我们可以以 $1$ 为根先跑一遍 dfs ，然后考虑 $d_i = \mathrm{LCA}(a_i,b_i)$ 的深度关系。
如果此时 $b_i$ 在 $a_i$ 的子树外，则 $a_i$ 的子树就是 $b_i$ 为根时的子树，且此时 $d_i = b_i$ 。
否则当 $d_i \ne b_i$ 时，$b_i$ 位于 $a_i$ 的子树内，则除了 $a_i$ 连向 $b_i$ 的那个儿子的子树，其他都会是新 $a_i$ 子树的一部分
LCA 以及 找某个节点对应的儿子，都可以通过倍增操作 $\mathcal{O}(\log n)$ 完成。
时间复杂度 $\mathcal{O}(n \log n)$ ，显然这不是最优解（所以下面还有一种解法）
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
#define LN 17
int n,m,pos=1,newP[N],head[N],head2[N];
int check_point,in[N],id[N],eid[N],o[N],sum[N],dep[N],fa[N][LN];
struct Edge { int u,v,next; } e[N * 6];
void addEdge(int u,int v,int *h) { e[++pos] = {u,v,h[u]}; h[u] = pos; }
void dfs(int u)
{
static int cnt = 0; o[++cnt] = u; id[u] = cnt;
for(int i = 0; i < LN - 1 && fa[u][i]; i++)
fa[u][i + 1] = fa[fa[u][i]][i];
for(int i = head[u],v; i; i = e[i].next)
if((v = e[i].v) != fa[u][0]) {
dep[v] = dep[u] + 1; fa[v][0] = u; dfs(v);
}
eid[u] = cnt;
}
int jump(int u,int d)
{
for(int i = LN - 1; ~i; i--)
if(dep[u] - (1 << i) >= d) u = fa[u][i];
return u;
}
int lca(int x,int y)
{
if(dep[x] < dep[y]) swap(x,y);
x = jump(x, dep[y]); if(x == y) return x;
for(int i = LN - 1; ~i; i--)
if(fa[x][i] != fa[y][i]) { x = fa[x][i], y = fa[y][i]; }
return fa[x][0];
}
bool fail() { while(n--) cout << "0\n"; return exit(0), 0; }
bool check(int u,int f)
{
for(int i = head[u],v; i; i = e[i].next)
if((v = e[i].v) != f) {
if(!newP[v])
{
addEdge(v,u,head2), newP[v] = u;
if(!check(v,u)) return false;
}else if(newP[v] != u) return false;
}
return true;
}
bool topo_sort()
{
queue<int> q; int cnt = 0;
for(int i = check_point; i <= pos; i++) ++in[e[i].v];
for(int i = 1; i <= n; i++) if(!in[i]) q.push(i), ++cnt;
for(int u; !q.empty(); )
{
u = q.front(); q.pop();
for(int i = head2[u]; i; i = e[i].next)
if(!(--in[e[i].v])) q.push(e[i].v), ++cnt;
}
return cnt == n;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m;
for(int i = 1, u,v; i < n; i++)
{
cin >> u >> v;
addEdge(u,v,head); addEdge(v,u,head);
}
check_point = pos + 1; dfs(1);
for(int i = 1, u,v,cu; i <= m; i++)
{
cin >> u >> v; addEdge(u,v,head2);
if(u == lca(u,v))
{
cu = jump(v, dep[u] + 1);
++sum[1]; --sum[id[cu]]; ++sum[eid[cu] + 1];
if(!check(u, cu)) fail();
}else
{
++sum[id[u]]; --sum[eid[u] + 1];
if(!check(u, fa[u][0])) fail();
}
}
if(!topo_sort()) fail();
for(int i = 1; i <= n; i++) sum[i] += sum[i - 1];
for(int i = 1; i <= n; i++) cout << char('0' | (!sum[id[i]])) << '\n';
return 0;
}（cxy：我为什么要先标记再判环啊？我就不能先判环吗？）
容易发现，如果原图是有解的，那么一定存在至少一个 $i$ 可以最后被删除（好像说了什么但什么都没说）
想想在推样例的时候你是怎么做的？显然是拓扑排序（cxy：我直接看题解的）
因此我们可以先通过拓扑排序求出一个可行的解 $\mathtt{rt}$，顺便还判断了原图是否无解。
然后我们还是像刚才一样，标记不可能成为根的点。可以证明，剩下的节点一定是可行的。
证明方法很简单，类似于换根dp，即考虑把 $\mathtt{rt}$ 换到相邻的点，显然我们只要改一下这条边的方向就可以了。
并且因为 $\mathtt{rt}$ 是一个可行解，标记的方法就简单多了，因为可行解一定是满足限制边的。（详见代码）
容易发现剩下的这些点都是连续的，所以我们只需要跑一个 dfs 就好了。
时间复杂度 $\mathcal{O}(n)$
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))
char vis[N]; queue<int> q;
int n,m,pos=1,ans[N],in[N],head[N],head2[N];
struct Edge { int u,v,next; } e[N * 4];
void addEdge(int u,int v,int *h) { e[++pos] = {u,v,h[u]}; h[u] = pos; }
int solve(int cnt = 0)
{
for(int u,v; !q.empty(); )
{
u = q.front(); q.pop(); ++cnt;
if(in[u] != 1)
{
if(in[u] < 1) return u;
while(n--) { cout << "0\n"; } return exit(0),0;
}
for(int i = head[u]; i; i = e[i].next)
{
v = e[i].v; --in[v]; ++cnt;
if(in[v] == 1) q.push(v);
}
for(int i = head2[u]; i; i = e[i].next)
{
v = e[i].v; --in[v]; ++cnt;
if(in[v] == 1) q.push(v);
}
}
if(cnt != n)
{
while(n--) cout << "0\n";
return exit(0), 0;
}
return -1;
}
void dfs(int u,int f)
{
ans[u] = 1;
for(int i = head[u]; i; i = e[i].next)
if(e[i].v != f && (!vis[e[i].v])) dfs(e[i].v, u);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m;
for(int i = 1, u,v; i < n; i++)
{
cin >> u >> v; ++in[u]; ++in[v];
addEdge(u,v,head); addEdge(v,u,head);
}
for(int i = 1, u,v; i <= m; i++)
{
cin >> u >> v;
addEdge(u,v,head2); ++in[v]; vis[u] = 1;
}
for(int i = 1; i <= n; i++) if(in[i] == 1) q.push(i);
int rt = solve(); dfs(rt, 0);
for(int i = 1; i <= n; i++) cout << ans[i] << '\n';
return 0;
}参考文献：
[1] https://www.luogu.com.cn/blog/Bartholomew/solution-p5157
[2] https://www.luogu.com.cn/blog/hongzy/the-cow-gathering
[3] https://yhx-12243.github.io/OI-transit/records/lydsy5485%3Blg5157.html
