题解：CF2062E1 The Game (Easy Version)

· · 题解

简单博弈论。

将点从大到小排序，显然取最大的点是先手必败态，考虑从最大的点向小的递推胜负状态。

由于题目要求我们输出一个先手必胜的节点即可，不妨假设我们输出的是符合条件的值最大的那个点。这样有什么好处呢，显然如果存在 u 的子树外的节点最大值小于等于 u 的值，u 一定是先手必败态，那么我们只需要找到满足除它的子树之外还有比他更大的点的值最大的那个点即可，因为选了这个点之后剩余的点一定转给对手先手必败态，Cirno 就赢了。

dfn 序加前后缀最大值维护即可，但是我傻傻地写了一个 st 表。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
const int maxn=4e5+20;
int t,n,a[maxn],dfn[maxn],st[maxn][24],tot,siz[maxn];
struct node{
    int val,id;
}rec[maxn];
inline bool cmp(node x,node y){
    return x.val>y.val;
}
vector<int> e[maxn];
void dfs(int u,int fa){
    dfn[u]=++tot,siz[u]=1;
    for(int v:e[u]){
        if(v==fa) continue;
        dfs(v,u);
        siz[u]+=siz[v];
    }
}
struct DS{
    inline void init(){
        for(int i=1;i<=n;i++) st[dfn[i]][0]=a[i];
        for(int i=1;i<=20;i++) for(int j=1;j<=n-(1<<i)+1;j++) st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
    }
    inline int ask(int x,int y){
        if(x>y) return 0;
        int k=log2(y-x+1);
        return max(st[x][k],st[y-(1<<k)+1][k]);
    }
}S;
inline int check(int x){
    int now=rec[x].id,lim=max(S.ask(1,dfn[now]-1),S.ask(dfn[now]+siz[now],n));
    return lim>rec[x].val;
}
inline void solve(){
    n=read(),tot=0;
    for(int i=1;i<=n;i++) a[i]=read(),e[i].clear(),rec[i]={a[i],i};
    int u,v;sort(rec+1,rec+1+n,cmp);
    for(int i=1;i<n;i++) u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
    dfs(1,0),S.init();
    for(int i=1;i<=n;i++) if(check(i)) return printf("%d\n",rec[i].id),void();
    printf("0\n");
}
int main(){
    t=read();
    while(t--) solve();
    return 0;
}