专栏文章

题解：CF2062E2 The Game (Hard Version)

__abcd_
CF2062E2题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqdqwn3
此快照首次捕获于
2025/12/04 03:08
3 个月前
此快照最后确认于
2025/12/04 03:08
3 个月前
查看原文

[CF2062E2] The Game (Hard Version)

E1\rm E1 的简单扩展，但是赛时在 F\rm F 上唐了一个多小时导致最后遗憾离场。
再阅读这篇题解前，请保证你已经会 E1\rm E1 的解法，否则可以移步至 这里。
假设你第一步删除了 xx，然后对手按照 E1\rm E1 的做法找到了比 xx 权值大的且先手必胜的点 yy，那你就炸了。因此我们需要保证：再删除 xx 后，所有权值比 xx 大的 yy，要么 yy 在 xx 的子树内，要么所有权值比 yy 大的且不在 yy 子树内的点 zz 都在 xx 的子树内。
那么当扫到 yy 时，只需要找到所有 zz 的 LCA\rm LCA，设为点 aa。那么 xx 要么是 yy 的祖先，要么是 aa 的祖先。可以再用一个 BIT\rm BIT 来判断这个条件。
关于如何找到 aa，只需要用一个 set\rm set 维护所有权值比 yy 大的点的 dfs\rm dfs 序，然后找到不在 yy 的子树内的 dfs\rm dfs 序最小的点 ll 和最大的点 rr，则 aa 就是 ll 和 rr 的 LCA\rm LCA。
最后复杂度是 O(nlog⁡n)O(n \log n)。
CPP
#include<bits/stdc++.h>
#define ll long long
#define pn putchar('\n')
#define mset(a,x) memset(a,x,sizeof a)
#define mcpy(a,b) memcpy(a,b,sizeof a)
#define all(a) a.begin(),a.end()
#define fls() fflush(stdout)
using namespace std;
int re()
{
    int x=0;
    bool t=1;
    char ch=getchar();
    while(ch>'9'||ch<'0')
        t=ch=='-'?0:t,ch=getchar();
    while(ch>='0'&&ch<='9')
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return t?x:-x;
}
const int maxn=1e6+5;
int n,m;
int dep[maxn];
int id[maxn],rid[maxn];
vector<int>a[maxn];
vector<int>e[maxn];
vector<int>ans;
set<int>b;
struct BIT
{
    int tree[maxn];
    void add(int x,int ad)
    {
        for(int i=x;i<=m;i+=i&-i)
            tree[i]+=ad;
    }
    int qry(int x)
    {
        int ret=0;
        for(int i=x;i;i-=i&-i)
            ret+=tree[i];
        return ret;
    }
    int qry(int l,int r)
    {
        return qry(r)-qry(l-1);
    }
}bit1,bit2;
int st[20][maxn];
int min2(int u,int v)
{
    return dep[u]<dep[v]?u:v;
}
int lca(int l,int r)
{
    if(!l||!r)
        return st[0][l|r];
    if(l>r)
        swap(l,r);
    int k=__lg(r-l+1);
    return min2(st[k][l],st[k][r-(1<<k)+1]);
}
void dfs(int pos,int fa)
{
    m++;
    id[pos]=m;
    st[0][m]=pos;
    for(int v:e[pos])
    {
        if(v==fa)
            continue;
        dep[v]=dep[pos]+1;
        dfs(v,pos);
        m++;
        st[0][m]=pos;
    }
    rid[pos]=m;
}
void solve()
{
    n=re();
    for(int i=1;i<=n;i++)
    {
        a[i].clear();
        e[i].clear();
    }
    for(int i=1;i<=n;i++)
        a[re()].push_back(i);
    for(int i=1;i<n;i++)
    {
        int u=re(),v=re();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    m=0;
    dfs(1,0);
    for(int j=1;j<=19;j++)
    {
        for(int i=1;i+(1<<j)-1<=m;i++)
            st[j][i]=min2(st[j-1][i],st[j-1][i+(1<<j-1)]);
    }
    for(int i=1;i<=m;i++)
        bit1.tree[i]=bit2.tree[i]=0;
    int cnt1=0,cnt2=0;
    b.clear();
    ans.clear();
    for(int k=n;k;k--)
    {
        for(int i:a[k])
        {
            if(bit1.qry(id[i],rid[i])<cnt1&&bit2.qry(id[i],rid[i])==cnt2)
                ans.push_back(i);
        }
        for(int i:a[k])
        {
            if(bit1.qry(id[i],rid[i])<cnt1)
            {
                auto l=b.lower_bound(id[i]),r=b.lower_bound(rid[i]);
                int t1=0,t2=0;
                if(l!=b.begin())
                {
                    l--;
                    t1=lca(*b.begin(),*l);
                }
                if(r!=b.end())
                    t2=lca(*r,*b.rbegin());
                int t=lca(id[t1],id[t2]);
                bit2.add(id[t],1);
                bit2.add(id[i],1);
                bit2.add(id[lca(id[t],id[i])],-1);
                cnt2++;
            }
        }
        for(int i:a[k])
        {
            cnt1++;
            b.insert(id[i]);
            bit1.add(id[i],1);
        }
    }
    sort(all(ans));
    printf("%d ",ans.size());
    for(int i:ans)
        printf("%d ",i);
    pn;
}
signed main()
{
    int T=re();
    while(T--)
        solve();
    return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...