[AGC010F] Tree Game

Genius_Star · 2024-05-25 11:51:53 · 题解

这里提供一个 O(N) 的拓扑排序算法。

思路：

先说结论：若一个点 u 为必胜点，必有一个它的儿子 son 满足 a_u > a_{son}，且 son 为必败点。

证明：

• 若 a_u \le a_{son}：

  • 则当先手移到别的点时，后手可以又将其移回来；这样可以不断耗死先手。

• 弱 a_u > a_{son}：

  • 则若后手执意要跳回 u，则先手可以又将其移到 son 这个点；这样可以耗死后手。

当一个点为叶子节点时，这个点肯定是必败点。

那么可以直接暴力枚举根，然后深搜一遍即可，时间复杂度为 O(N^2)。

考虑优化，因为若 v 能对 u 造成影响当且仅当 a_u > a_v，且 v 是 u 的儿子。

那么建图的时候就可以按照 a_u,a_v 的大小建单向边。

此时进行拓扑排序即可。

时间复杂度优化为 O(N)。

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const ll N=3030;
inline ll read(){
    ll 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;
}
inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
      write(x/10);
    putchar(x%10+'0');
}
ll n;
ll a[N],d[N];
bool f[N];
vector<ll> E[N];
void add(ll u,ll v){
    E[u].push_back(v);
    d[v]++;
}
void topo(){
    queue<ll> q;
    for(int i=1;i<=n;i++)
      if(!d[i])
        q.push(i);
    while(!q.empty()){
        ll u=q.front();
        q.pop();
        for(auto v:E[u]){
            if(!f[u])
              f[v]=1;
            if(!--d[v])
              q.push(v);
        }
    }
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)
      a[i]=read();
    for(int u,v,i=1;i<n;i++){
        u=read(),v=read();
        if(a[u]>a[v])
          add(v,u);
        if(a[u]<a[v])
          add(u,v);
    }
    topo();
    for(int i=1;i<=n;i++){
        if(f[i]){
            write(i);
            putchar(' ');
        }
    }
    return 0;
}