提出 #73686851

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(t,l,r) for(int t=l;t<=r;t++)
#define per(t,l,r) for(int t=r;t>=l;t--)
const int N=200005,MOD=998244353;
int n,m,U[N],V[N],f[N],pw[N],dep[N],fa[N][20],fe[N],h[N],tot,mst[N];
struct E {int to,id,nxt;} e[N*2];
vector<int> g[N];
void add(int u,int v,int id) {e[++tot]={v,id,h[u]};h[u]=tot;}
int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
void dfs1(int u,int p,int d,int id) {
    dep[u]=d;fa[u][0]=p;fe[u]=id;
    rep(i,1,19) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=h[u];i;i=e[i].nxt) if(e[i].to!=p) dfs1(e[i].to,u,d+1,e[i].id);
}
int lca(int u,int v) {
    if(dep[u]<dep[v]) swap(u,v);
    per(i,0,19) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    if(u==v) return u;
    per(i,0,19) if(fa[u][i]!=fa[v][i]) {u=fa[u][i];v=fa[v][i];}
    return fa[u][0];
}
signed main() {
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;pw[0]=1;rep(i,1,m) pw[i]=pw[i-1]*2%MOD;
    rep(i,1,n) f[i]=i;
    rep(i,1,m) cin>>U[i]>>V[i];
    per(i,1,m) {
        int x=find(U[i]),y=find(V[i]);
        if(x!=y) {f[x]=y;mst[i]=1;add(U[i],V[i],i);add(V[i],U[i],i);}
    }
    dfs1(1,0,1,0);
    rep(i,1,m) {
        if(mst[i]) continue;
        int u=U[i],v=V[i],p=lca(u,v);
        while(u!=p) {g[u].push_back(i);u=fa[u][0];}
        while(v!=p) {g[v].push_back(i);v=fa[v][0];}
    }
    int mn=m+1,be=-1;
    rep(i,2,n) {
        int mx=fe[i];
        for(int x:g[i]) if(x>mx) mx=x;
        if(mx<mn) {mn=mx;be=i;}
    }
    int ans=pw[fe[be]];
    for(int x:g[be]) ans=(ans+pw[x])%MOD;
    cout<<ans<<"\n";
    return 0;
}

提出情報

ジャッジ結果