题解 | 大型聚会-牛客假日团队赛1K题

题目描述

奶牛们从世界各地聚集起来参加一场大型聚会。总共有 $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≤x_i,y_i≤N，x_i≠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$ 先离开聚会。

输入保证 $1≤N,M≤10^5$ 。对于占总分20%的测试数据，保证 $N,M≤3000$ 。

输出描述:

输出 $N$ 行，每行包含一个整数 $d_i$ ，如果奶牛 $i$ 可以成为最后一头离开的奶牛，则 $d_i=1$ ，否则 $d_i=0$ 。

示例1

输入

5 1
1 2
2 3
3 4
4 5
2 4

输出

0
0
1
1
1

解答

给你一棵 $N$ 个节点的树，每次删去一个叶子节点，直到剩下一个节点

但是有 $M$ 个限制 $a,b$ ，表示如果 $a$ 没被删除， $b$ 不能删除

最后输出所有能成为最后一个节点的节点

显而易见，对于每个限制，以 $b$ 为根时 $a$ 的子树（包括自己）都是不可行点

于是我们可以写出一个支持子树修改和换根数据结构，比如 $Top \ Tree$ ，树链剖分（参见 $LOJ139$ ）

但是单单这个结论是不够的，我们观察一下这组数据

3 2
1 2
2 3
1 3
3 1

0
0
0

我们的程序会输出

0
1
0

因为没有考虑无解情况

那么如何考虑无解情况呢

该题中的无解就是指没有一个点是可行点，那么我们其实只要找出任何一个可行点就可以了

怎么找？

我们将树上的 $n−1$ 条边连成双向边，将限制里的 $a$ 连向 $b$ 一条单向边

那么，我们每次就只能删除入度为 $1$ 的点

因为如果这个点不是叶子节点，入度至少为 $2$ ，如果有被连有向边（被约束），入度也至少为 $2$

随便找一个入度为 $1$ 的点删除，接下来将它连向的边都删除（也就是说连向的点入度--），然后如果更新后连向的点的入度为 $1$ （不需要每次 $O(n)$ 统计，只统计这次删除更新的点就行了），加入待定删除点

最后，如果还没有删除 $n−1$ 个点就无法继续删了（没有入度为 $1$ 的点了，比如每个点都被互相约束），说明无解，否则有解

这部分代码（为了方便第二种解法，我用了 $vector$ 存（ $to$ 是双向边， $d$ 是单向边））：

queue<int>q;
int findroot()
{
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        if(!deg[x]/*入度*/)return x;
        for(int i=0;i<to[x].size();i++)
        {
            if(--deg[to[x][i]]==1)
            {
                q.push(to[x][i]);
            }
        }
        for(int i=0;i<d[x].size();i++)
        {
            if(--deg[d[x][i]]==1)
            {
                q.push(d[x][i]);
            }
        }
    }
    return 0;
}

这样写的话，时间复杂度为 $O(m log2 m)$

代码：咕咕咕

但是我们刚刚那个方法显然不够优( $hyf:$ 太暴力了)，虽然足以通过本题，但是如果数据加到 $3e6$ ，显然过不了（吧，有松松松真传我也没办法2333）

首先我们要证(kou)明(hu)两个结论：

一，可行点连通

因为每次修改不可行点只是修改子树，并不破坏可行点的连通性，所以成立

二，任意一个可行点作为根，删除每个限制中的 $a$ 的子树，剩下的都是可行点

这个我真不会证，我的想法是将可行点看为树的中间部分，不可行点是树的一些边角，从中间往四周边角扩散不需要考虑从哪里开始，由于可行点连通，所以不需要每次换根

我们将 $a$ 的位置打上标记，以 $findroot$ 的返回值（任意一个可行点）为起始点，遇到标记直接 $return$ ，最后输出答案即可

时间复杂度： $findroot O(n) ，dfs O(n)$

总时间复杂度 $O(n)$

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<int>to[100001],d[100001];
queue<int>q;
int n,m,deg[100001];
bool vis[100001],ans[100001];
int findroot()
{
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        if(!deg[x])return x;
        for(int i=0;i<to[x].size();i++)
        {
            if(--deg[to[x][i]]==1)
            {
                q.push(to[x][i]);
            }
        }
        for(int i=0;i<d[x].size();i++)
        {
            if(--deg[d[x][i]]==1)
            {
                q.push(d[x][i]);
            }
        }
    }
    return 0;
}
void dfs(int x,int f)
{
    ans[x]=1;
    for(int i=0;i<to[x].size();i++)
    {
        if(!vis[to[x][i]]&&f!=to[x][i])
        {
            dfs(to[x][i],x);
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        to[x].push_back(y);
        to[y].push_back(x);
        deg[x]++;
        deg[y]++;
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        d[x].push_back(y);
        deg[y]++;
        vis[x]=1;
    }
    for(int i=1;i<=n;i++)
    {
        if(deg[i]==1)q.push(i);
    }
    int root=findroot();
    dfs(root,0);
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}

来源：千柒/Kan_kiz