[ABC350G] Mediator

_qingshu_ · 2024-04-21 14:41:56 · 题解

感觉下位蓝或者上位绿吧，挺简单的启发式合并裸题。

题意：

给定 N 个点，M 次操作，操作强制在线，操作分为：

将点 u,v 之间连一条边。
询问同时与 u,v 直接相连的一个点，如果没有输出 0。

然后数据保证无重边无自环，任意时刻图为一个森林，所以操作二答案唯一。

思路：

一眼启发式合并，如果操作可能有答案那么这两个点一定在同一颗树内且距离为 2，考虑在随意钦定根的情况下答案的分类讨论，容易发现如果记录 fa_{i} 为点 i 的父亲节点，当 fa_{i}=i 时点 i 为根，那么答案有且仅有五种情况：

如果以上均不满足，那么答案不存在，答案是 0。

解决了询问，我们来考虑连边，发现如果要保证是森林的话一次连边等价于合并两颗树，但是我们要保证合并后的大树的根唯一，那么也就是说被合并的树一定是以 v 为根节点的，所以我们考虑怎么将一棵树的根节点变成 v。

我们可以想一想对于原树与新树需要更改的 fa_{i}，你会发现把所有的需要被更改的点连起来就是一条从 v 到原树根的链，下面是口胡证明（并不严谨，但是是对的，感性理解qwq）：

我们把原树所有的点分为 4 类：

以 v 为根节点的子树内的所有节点，对于原树和新树来说，它们都是满足到根路径经过点 v 的，所以不需要更改，在 fa_{v} 的更改后自然指向大树的根。
从点 v 到原根的路径上的点，这些点均为指向有误，是需要更改方向变为从原根指向 v。
以点 i 为根节点且满足 fa_{i} 在从 v 到根的链上的子树，它们在第二类的点更改后自然随之指向大树的根。
以点 i 为根且满足 fa_{i} 为原根的子树，这些点在原根指向更改后随之指向大树的根。

综上，我们换根的过程仅需要跑一边从 v 到原根的路径就可以保证换根后所有的点父亲指向均正确。

然后这个复杂度是 \mathcal{O}(N^2) 的，但是我们可以启发式合并优化到 \mathcal{O}(N\log(N))，树的大小可以用并查集维护。

Code：

#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
int ans,a,b,c,n,q,lastans,fa[100010],root[100010],siz[100010],fab,fac;
inline int findfa(int x){
    if(root[x]!=x)root[x]=findfa(root[x]);
    return root[x];
}
inline void cg(int x){
    if(fa[x]==x)return;
    cg(fa[x]),fa[fa[x]]=x;
}
inline void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        fa[i]=root[i]=i;siz[i]=1;
    }
    while(q--){
        cin>>a>>b>>c;
        a=1+((1ll*a*(1+lastans))%mod)%2;
        b=1+((1ll*b*(1+lastans))%mod)%n;
        c=1+((1ll*c*(1+lastans))%mod)%n;
        if(a==1){
            fab=findfa(b);fac=findfa(c);
            if(siz[fac]>siz[fab])swap(b,c),swap(fab,fac);
            siz[fab]+=siz[fac];
            cg(c);fa[c]=b;root[fac]=fab;
        }
        else{
            lastans=0;
            if(fa[c]==b||fa[b]==c);
            else if(fa[c]==fa[b]||fa[fa[c]]==b)lastans=fa[c];
            else if(fa[fa[b]]==c)lastans=fa[b];
            cout<<lastans<<"\n";
        }
    }
}
int main(){
    int T=1;//cin>>T;
    while(T--)solve();
}

加上快读可以跑进 10ms，目前 2024.4.21 的最优解。