P10674 题解

· · 题解

Problem Link

题目大意

给定 n 个点 m 条边的无向图，求有多少点集对 (S,T) 使得每个 S 中元素都在某两个 T 中元素的某条简单路径上。

数据范围：n\le 5\times 10^5,m\le10^6 。

思路分析

对每个 T，求出其内部所有路径并构成的点集 V(T)，那么 S 的选法就是 2^{|V(T)|} 种方案。

考虑刻画 f(T)，容易发现建出原图的圆方树，那么所有 T 中节点所在的方点生成的斯坦纳树上的点都在 V(T) 中，如果是方点，那么其对应的所有圆点都在 V(T) 中。

考虑在方点处统计权值，对于一个大小为 C 的点双连通分量，设其权值为 2^{C-1}，即圆方树上儿子个数。

那么对于斯坦纳树的根，如果其是圆点，那么没有将这个点考虑在 V(T) 中，否则没有将其父亲对应的圆点考虑进 V(T) 中，因此答案最后 \times 2 再加上 T=\varnothing 的情况即可。

dp 时设 f_u 表示 u 子树内至少有一个点被选入 T 时的权值和，即钦定 u 子树外选点后的答案。

但是我们在统计点 u 作为树根的权值的时候要钦定至少两棵子树被选，做一个简单背包即可。

时间复杂度 \mathcal O(n+m)。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+5,MOD=998244353;
ll dp[MAXN],ans,pw[MAXN];
vector <int> G[MAXN],E[MAXN];
void link(int x,int y) { E[x].push_back(y),E[y].push_back(x); }
int n,m,k,low[MAXN],dfn[MAXN],dcnt,stk[MAXN],tp,w[MAXN];
bool ins[MAXN];
void tarjan(int u) {
    ins[stk[++tp]=u]=true,dfn[u]=low[u]=++dcnt;
    for(int v:G[u]) {
        if(!dfn[v]) {
            tarjan(v),low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]) {
                link(++k,u);
                while(ins[v]) link(stk[tp],k),++w[k],ins[stk[tp--]]=false;
            }
        } else low[u]=min(low[u],dfn[v]);
    }
}
void dfs(int u,int fz) {
    if(E[u].size()==1&&fz!=0) return ++ans,dp[u]=1,void();
    ll g[3]={1,0,0};
    for(int v:E[u]) if(v^fz) {
        dfs(v,u),g[2]=(g[2]*(dp[v]+1)+g[1]*dp[v])%MOD,g[1]=(g[1]+g[0]*dp[v])%MOD;
    }
    if(u>n) ans=(ans+g[2]*pw[w[u]])%MOD,dp[u]=(g[2]+g[1])*pw[w[u]]%MOD;
    else ans=(ans+2*g[2]+g[1]+g[0])%MOD,dp[u]=(2*g[2]+2*g[1]+g[0])%MOD;
}
signed main() {
    scanf("%d%d",&n,&m),k=n;
    for(int i=pw[0]=1;i<=n;++i) pw[i]=pw[i-1]*2%MOD;
    for(int i=1,u,v;i<=m;++i) {
        scanf("%d%d",&u,&v),G[u].push_back(v),G[v].push_back(u);
    }
    tarjan(1),dfs(1,0);
    printf("%lld\n",(2*ans+1)%MOD);
    return 0;
}