id="p10674-mx-s1-t3-电动力学-题解">P10674

[MX-S1-T3]

inline">\(S\)，为了证明这一点，我们需要一个观察。

inline">\(x,y,s\)，则必然存在一条从

src="https://img2024.cnblogs.com/blog/2950259/202510/2950259-20251031202300879-314420670.png"

alt=""

inline">\(U_1,U_2\)，

class="math

inline">\(V_1,V_2\)，现在我们说明，使用这些路径能构造出我们想要的路径。

假设存在一对

满足他们不交，那么选择这两条路径即可。

假设这种路径对不存在，我们考虑取

inline">\(U_2\)，若将其上的点按从

inline">\(a_1=x,a_2,a_3,\dots,a_k=s\)，找到最小的

inline">\(j<i\)，

class="math

inline">\(x\stackrel{U_2}{\longrightarrow}

a_i\stackrel{V_1}{\longrightarrow}

s\stackrel{V_2}{\longrightarrow}y\)，构造完成。

命题得证。

---

有了这一观察，我们就很容易证明上述结论，对路径上进入点双和离开点双的点应用上述观察即可。

我们设圆方树上圆点

inline">\(2^{s_x-1}\)，其中

inline">\(\prod_{x}v_x,\text{where

}\exists

T,x\in\operatorname{path}(a,b)\)，其中

inline">\(\operatorname{path}(a,b)\)

表示树上

src="https://img2024.cnblogs.com/blog/2950259/202510/2950259-20251031202301929-1587141330.png"

alt=""

\left(f_v+1\right)-1\right)\times2^{s_x-1}\)

\left(f_v+1\right)-1\right)-1\)

\left(f_v+1\right)+\sum_{P\subseteq

S,|P|\ge

说人话就是，如果选择这个点，那么子树随便怎么都行，如果不选

的原因是要排除相邻方点之间的割点，但是现在多排除了一个点，最后需要乘以

inline">\(S=T=\emptyset\)

class="language-cpp">#include<bits/stdc++.h>

using

y){e[x].push_back(y),e[y].push_back(x);

int

tim,dfn[N],low[N],nC,siz[N];stack<int>

stk;

x){low[x]=dfn[x]=++tim,stk.push(x);for(int

v:e[x]){if(!dfn[v]){Tarjan(v);low[x]=min(low[x],low[v]);if(low[v]>=dfn[x]){++nC;int

cur;add(rst,nC,x),siz[nC]++;do{cur=stk.top(),stk.pop();add(rst,cur,nC),siz[nC]++;}while(cur!=v);}}else

pw2[N],ans;

continue;DP(v,x),prod=prod*(f[v]+1)%P,sum=(sum+f[v])%P;}if(x>n){f[x]=(prod-1)*pw2[siz[x]-1]%P;prod=(prod-1-sum)%P;ans=(ans+prod*pw2[siz[x]-1]%P)%P;}else{ans=(ans+prod)%P,f[x]=prod*2ll%P-1;prod=(prod-1-sum)%P,ans=(ans+prod)%P;}

int

main(){ios::sync_with_stdio(false),cin.tie(nullptr);cin>>n>>m;pw2[0]=1;for(int

i=1,u,v;i<=m;i++)

cin>>u>>v,add(e,u,v);for(int

i=1;i<=n;i++)

pw2[i]=pw2[i-1]*2ll%P;nC=n,Tarjan(1),DP(1,0);cout<<((2ll*ans%P+1)%P+P)%P;

role="contentinfo">

本文来自博客园，作者：haozexu，转载请注明原文链接：https://www.cnblogs.com/haozexu/p/19181201