自动搬运

查看原文

来自洛谷，原作者为

	xieziheng 还不是因为我动了资本的蛋糕

搬运于2025-08-24 23:00:09，当前版本为作者最后更新于2024-06-30 12:11:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题真的只有蓝吗。。。看来是我太菜了

不过我竟然场切了 dp，感到震惊。

这个题首先要选择一个好算的东西计数，如果考虑对每个 $S$ 算 $T$ 的方案就很不好搞，所以反过来，考虑对每个 $T$ 算有多少个 $S$ 满足条件。$|T|\leq 1$ 是平凡的，一下设 $|T|\geq 2$。

先看树的情况，是显然的，$S$ 中的点必定在 $T$ 中所有点构成的虚树中，且这是充要的，换言之，设 $T$ 中点构成的虚树大小为 $m$，则共有 $2^m$ 的 $S$ 满足条件。

考虑推广。发现“简单路径”很像点双相关（说句闲话，我比赛以为简单路径指的是边不重复）。于是大胆猜测构成的是所有有 $|T|$ 中路径经过的点双的并集大小。证明是容易的，由点双性质可知。

所以考虑建出圆方树 dp。这时候就需要给圆方树上每个点赋权，使得答案容易计算。发现可以这样赋值：对于圆点，权值为 $0$，对于方点 $x$，权值为 $s_x-1$，$s_x$ 表示第 $x$ 个点双的大小。这样所有有 $|T|$ 中路径经过的点双的并集大小即为所有 $T$ 中的点在圆方树上构成的虚树中的点的权值和加一，设这个玩意为 $F(T)$。即求 $\sum_{T} 2^{F(T)}=2\sum_{T} 2^{F(T)-1}$。

考虑 dp，设 $f_x$ 表示虚树根为 $x$ 的方案数。考虑合并子树状态，一定为选择若干个在 $x$ 的不同子树的点，然后对其求和。设 $g(y,x)$ 表示对于 $x$ 为 $y$ 的祖先，$x$ 到 $y$ 路径上的权值和（不包含 $y$），设 $t_x=\sum_{y\in S_x} f_y2^{g(y,x)}$，$S_x$ 表示 $x$ 的子树构成的集合，同理定义 $T_x$ 表示 $x$ 所有儿子构成的集合。

• $x$ 为方点，则一定为选择大于等于 $2$ 个子树中的点合并。则 $f_x=2^{s_x-1}((\prod_{y\in T_x}(1+t_y))-1-\sum_{y\in T_x}t_y),t_x=2^{s_x-1}\sum_{y\in T_x}t_y$。

• $x$ 为原点，则 $f_x=(2\prod_{y\in T_x}(1+t_y))- 1-\sum_{y\in T_x}t_y$。

这样就做完了，复杂度 $\mathcal{O}(n)$

细节见代码：

#include <bits/stdc++.h>
#define il inline
using namespace std;
typedef long long ll;
const ll mod=998244353;
il int read(){
    int x=0,c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-48,c=getchar();
    return x;
}
il void add(ll &x,ll y){x=(x+y>=mod?x+y-mod:x+y);}
const int N=1e6+5;
int n,m,dfn[N],low[N],cnt,st[N],top,bel[N],idx,siz[N];ll ans,pw[N],f[N],s[N],t[N];
vector<int> e[N],g[N];
il void adde(int x,int y,vector<int> e[]){e[x].push_back(y),e[y].push_back(x);}
void tarjan(int x,int fath){
    int y,z;dfn[x]=low[x]=++cnt,st[++top]=x;
    for(int y:e[x]){
        if(y==fath) continue;
        if(!dfn[y]){
            tarjan(y,x),low[x]=min(low[x],low[y]);
            if(low[y]>=dfn[x]){
                ++idx,adde(idx+n,x,g),bel[x]=idx,siz[idx+n]=1;
                do{
                    z=st[top--],bel[z]=idx,adde(idx+n,z,g),++siz[idx+n];
                }while(z!=y);
            }
        }
        else low[x]=min(low[x],dfn[y]);
    }
}
void dfs(int x,int fath){
    if(x>1 && g[x].size()==1){
        f[x]=s[x]=t[x]=1;
        return ;
    }
    ll u=0,v,w=1ll;
    for(int y:g[x]){
        if(y==fath) continue;
        dfs(y,x),add(s[x],s[y]);
    }
    if(x>n){
        for(int y:g[x]){
            if(y==fath) continue;
            add(u,t[y]),w=(w*(1ll+t[y]))%mod,t[x]=(t[x]+pw[siz[x]-1]*t[y])%mod;
        }
        f[x]=((w-1ll-u+mod)*pw[siz[x]-1])%mod;
    }
    else{
        for(int y:g[x]){
            if(y==fath) continue;
            add(u,t[y]),w=(w*(1ll+t[y]))%mod,add(t[x],t[y]);
        }
        f[x]=(u+(w-u+mod)*2ll-1)%mod;
    }
    add(s[x],f[x]),add(t[x],f[x]);
}
int x,y,z;ll u,v,w;
int main(){
    scanf("%d%d",&n,&m);pw[0]=1ll;
    for(int i=1;i<=n;++i) pw[i]=(pw[i-1]*2ll)%mod;
    for(int i=1;i<=m;++i) x=read(),y=read(),adde(x,y,e),adde(y,x,e);
    tarjan(1,0);
    dfs(1,0);
    for(int i=1;i<=n+idx;++i) add(ans,f[i]);
    printf("%lld",(2ll*ans+1ll)%mod);
    return 0;
}