洛谷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 i N $ 行，每行包含两个整数 $ x_i $ 和 $ y_i $ ，满足 $1 \leq x_i,y_i \leq N,~x_i \neq y_i$ ，表示奶牛 $ x_i $ 和奶牛 $ y_i $ 是朋友关系。

输入的第 $ N+1 i N+M $ 行，每行包含两个整数 $ a_i $ 和 $ b_i $ ，满足 $ 1 a_i,b_i N $ ， $ a_i 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;
}