CF2042E 题解

笨方法做题。

考虑如何找出最大的需要保留的点，发现我们可以二分点权值

x

，删掉比

x

大的点后看是否存在一个连通块具有所有颜色。这样我们就在

O(n\log n)

时间内找到了一个答案的必须点。

接下来我们先视为保留

[1,x]

的所有点，然后再进行删点。将

x

视为根，则我们后面要删掉点

u

时需要满足删完

u

后照样拥有所有颜色。这样的点

u

必然不满足子树内有一个唯一颜色或有一个颜色的两个点。倒推可得我们从每个颜色的两个点的 lca 向上标记，这些点都是不可删除的；而对于唯一颜色点直接从他本身向上标记。标记只有

O(n)

个，复杂度是显然正确的。

时间复杂度：

O(n\log n)

。但是由于前面那个二分的过程，常数很大，需要一定卡常。。

代码：

CPP

#include <bits/stdc++.h>
using namespace std;
const int N=4e5+5;
char buf[1<<21], *p1, *p2;
#define GC p1 == p2 and (p2 = (p1 = buf) + fread(buf, 1, 1<<21, stdin), p1 == p2) ? EOF : *p1++
inline int read() {
	int x = 0; char ch = GC;
	while(ch > '9' || ch < '0') ch = GC;
	while(ch >= '0' && ch <= '9') x = (x<<1) + (x<<3) + (ch^48), ch = GC;
	return x;
}
bool qwqa;
int n,a[N],head[N],etot,vis[N],ok,c[N],rt,fa[N],b[N][3],ans[N],cnt,dfn[N],f[20][N<<1],num,d[N];
struct edge{
    int nxt,to;
}e[N<<1];
inline void add(int a,int b){
    e[++etot]={head[a],b};head[a]=etot;
}
inline void dfs1(int x,int w){
    if(!c[a[x]])ok++;
    c[a[x]]=1;vis[x]=1;
    for(int i = head[x],y;i;i=e[i].nxt){
        y=e[i].to;
        if(!vis[y]&&y<w)dfs1(y,w);
    }
}
inline void dfs2(int x,int w){
    c[a[x]]=0;
    vis[x]=2;
    for(int i = head[x],y;i;i=e[i].nxt){
        y=e[i].to;
        if(vis[y]==1&&y<w)dfs2(y,w);
    }
}
inline bool check(int x){
    for(int i = 1;i<=2*n;i++)vis[i]=0;
    for(int i = 1;i<=2*n;i++){
        if(!vis[i]&&i<x){
            ok=0;
            dfs1(i,x);dfs2(i,x);
            if(ok==n)return 1;
        }
    }
    return 0;
}
inline void dfs(int x,int fa){
    c[a[x]]++;vis[x]=0;
    b[a[x]][c[a[x]]]=x;
    ::fa[x]=fa;
    dfn[x]=++num;f[0][num]=x;
    for(int i = head[x],y;i;i=e[i].nxt){
        y=e[i].to;
        if(y!=fa&&y<=rt)d[y]=d[x]+1,dfs(y,x),f[0][++num]=x;
    }
}
inline void dfs3(int x){
    vis[x]=2;
    int now = b[a[x]][1];
    if(now==x)now=b[a[x]][2];
    while(!vis[now]){
        vis[now]=1;
        now=fa[now];
    }
    for(int i = head[x],y;i;i=e[i].nxt){
        y=e[i].to;
        if(y!=fa[x]&&y<=rt)dfs3(y);
    }
}
inline int lca(int x,int y){
    x=dfn[x],y=dfn[y];
    if(x>y)swap(x,y);
    int k = __lg(y-x+1);
    if(d[f[k][x]]<d[f[k][y-(1<<k)+1]])return f[k][x];
    return f[k][y-(1<<k)+1];
}
bool qwqb;
int main(){
    // cerr<<(&qwqa-&qwqb)/1024/1024;
    n=read();
    for(int i = 1;i<=2*n;i++)a[i]=read();
    for(int i = 1,x,y;i<2*n;i++)x=read(),y=read(),add(x,y),add(y,x);
    int l=n+1,r=2*n,mid,qwq=0;
    while(l<=r){
        qwq++;
        mid=l+r>>1;
        if(check(mid))r=mid-1;
        else l=mid+1;
    }
    // if(n==2e5)return 0;
    rt=r;
    for(int i = 1;i<=2*n;i++)vis[i]=2;
    d[rt]=1;dfs(rt,0);
    for(int j = 1;j<=__lg(num);j++){
        for(int i = 1;i+(1<<j)-1<=num;i++){
            if(d[f[j-1][i]]<d[f[j-1][i+(1<<j-1)]])f[j][i]=f[j-1][i];
            else f[j][i]=f[j-1][i+(1<<j-1)];
        }
    }
    vis[rt]=1;
    for(int i = 1;i<=n;i++){
        if(c[i]==1){
            int now = b[i][1];
            while(!vis[now]){
                vis[now]=1;
                now=fa[now];
            }
        }
        else{
            int now=lca(b[i][1],b[i][2]);
            while(!vis[now]){
                vis[now]=1;
                now=fa[now];
            }
        }
    }
    ans[++cnt]=rt;
    for(int i = rt-1;i>=1;i--){
        if(vis[i]==2)continue;
        if(vis[i]){
            ans[++cnt]=i;
            continue;
        }
        dfs3(i);
    }
    printf("%d\n",cnt);
    for(int i = cnt;i>=1;i--)printf("%d ",ans[i]);
    return 0;
}

文章操作

相关推荐

评论

CF2042E 题解