题目：https://loj.ac/problem/2547
一条树边 cr->v 会被计算 ( n-siz[v] ) * siz[v] 次。一条环边会被计算几次呢？于是去写了斯坦纳树。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
int Mx(int a,int b){return a>b?a:b;}
int Mn(int a,int b){return a<b?a:b;}
const int mod=1e9+;
int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;}
int pw(int x,int k)
{int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;} int n,m;
namespace S1{
const int N=,M=(<<)+;
int hd[N],xnt,to[N<<],nxt[N<<];
int bin[N],dp[N][M],dis[N][N]; bool vis[N];
queue<int> q;
void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}
void init()
{
for(int i=;i<=n;i++)
{
memset(vis,,sizeof vis);
q.push(i); vis[i]=;
while(q.size())
{
int k=q.front(); q.pop();
for(int i=hd[k],v;i;i=nxt[i])
if(!vis[v=to[i]])
{ vis[v]=;dis[i][v]=dis[i][k]+;q.push(v);}
}
}
bin[]=;for(int i=;i<=n;i++)bin[i]=bin[i-]<<;
}
void solve()
{
for(int i=,u,v;i<=m;i++)
u=rdn(),v=rdn(),add(u,v),add(v,u);
init();
memset(dp,0x3f,sizeof dp);
for(int i=;i<=n;i++)dp[i][bin[i-]]=;
int ans=;
for(int s=;s<bin[n];s++)
{
for(int i=;i<=n;i++)
for(int t=(s-)&s;t;t=(t-)&s)
dp[i][s]=Mn(dp[i][s],dp[i][t]+dp[i][s^t]);
for(int i=;i<=n;i++)q.push(i),vis[i]=;
while(q.size())
{
int k=q.front(); q.pop(); vis[k]=;
for(int i=hd[k],v;i;i=nxt[i])
if(dp[v=to[i]][s]>dp[k][s]+)
{
dp[v][s]=dp[k][s]+;
if(!vis[v])q.push(v),vis[v]=;
}
}
int mn=dp[][s];
for(int i=;i<=n;i++)mn=Mn(mn,dp[i][s]);
ans=upt(ans+mn);
}
ans=(ll)ans*pw(bin[n],mod-)%mod;
printf("%d\n",ans);
}
}
int main()
{
n=rdn();m=rdn();
if(n<=){S1::solve();return ;}
return ;
}
不应从每条环边的角度考虑，而要从每个环的角度考虑。思维还是不足。
想算一个环上有 len 条边被选的方案。
记一个“环外子树（含自己这点）中有点被选的环上点” 为 “被选的点” 。
首先考虑如果有一个选点方案，这个环会被怎么选边。为了把点都连通，被选的点两两之间应该连通。
所以环上没被选的边一定是最远的两个相邻的被选的点之间的部分。
想求一个环 “最远相邻被选点的间隔为 len ” 的方案。注意到 “最远相邻被选点的间隔 <=len ”的方案容易 DP 。
断环成链，dp[ i ][ j ] 表示 i 点和 j 点要选，[ i , j ] 之间被选点间隔 <=len 的方案。则 \( dp[i][j]=f[j]*\sum\limits_{k=j-len}^{j-1}dp[i][k] \) ，其中 \( f[j] \) 是选 j 点的方案，即 ( 2环外子树大小 -1 ) 。
前缀和优化即可。对于一个 len ，合法的 dp[ i ][ j ] 应该满足 (cnt - j) + i <=len （cnt 是环点个数）。把这些加到 g[ len ] 上，用 (cnt-len) * (g[ len ] - g[ len-1 ]) 贡献答案即可。
求环外子树大小要小心。注意清空数组。注意分辨不同的环。可以给环最浅的点打标记，特殊求该点的环外子树大小。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int Mx(int a,int b){return a>b?a:b;}
int Mn(int a,int b){return a<b?a:b;}
const int N=,M=N<<,mod=1e9+;
int upt(int x){while(x>=mod)x-=mod;while(x<)x+=mod;return x;}
int pw(int x,int k)
{int ret=;while(k){if(k&)ret=(ll)ret*x%mod;x=(ll)x*x%mod;k>>=;}return ret;} int n,m,hd[N],xnt,to[M],nxt[M],spe[N];
int dp[N],pr[N],f[N],g[N],siz[N],ans,bin[N];
int tim,dfn[N],low[N],sta[N],top,cnt,col[N],qnt,q[N];
bool vis[N],ins[N];
void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}
void tarjan(int cr,int fa)
{
dfn[cr]=low[cr]=++tim; sta[++top]=cr; ins[cr]=;
siz[cr]=;
for(int i=hd[cr],v;i;i=nxt[i])
if((v=to[i])!=fa)
{
if(!dfn[v])
{tarjan(v,cr);low[cr]=Mn(low[cr],low[v]);siz[cr]+=siz[v];}
else if(ins[v])low[cr]=Mn(low[cr],dfn[v]);
}
if(dfn[cr]==low[cr])
{
if(sta[top]==cr){ins[cr]=;top--;return;}
cnt++;
do{int v=sta[top];ins[v]=;col[v]=cnt;}while(sta[top--]!=cr);
spe[cr]=fa;//fa can be 0 but no influence
}
}
void dfsx(int cr)
{
q[++qnt]=cr; vis[cr]=; int id=qnt;
for(int i=hd[cr],v;i;i=nxt[i])
if(!vis[v=to[i]]&&col[v]==col[cr])dfsx(v);//col==
else if(col[v]!=col[cr]&&v!=spe[cr])//include !col
f[id]+=siz[v];//col!= not !col//v!=spe[cr]
if(spe[cr])
f[id]+=n-siz[cr];//+= not =//n-siz[cr] not spe-siz[cr]
f[id]++;
}
void solve(int cr)
{
for(int i=;i<=qnt;i++)f[i]=; qnt=;//f[i]=0//qnt=0
dfsx(cr);
for(int len=;len<=qnt;len++)
{
g[len]=;
for(int i=;i<=len;i++)
{
dp[i]=bin[f[i]]; pr[i]=dp[i]; pr[i-]=;
int lm=qnt-len+i;
if(i>=lm)g[len]=upt(g[len]+dp[i]);
for(int j=i+;j<=qnt;j++)
{
dp[j]=(ll)upt(pr[j-]-pr[Mx(i,j-len)-])*bin[f[j]]%mod;
pr[j]=upt(pr[j-]+dp[j]);
if(j>=lm)g[len]=upt(g[len]+dp[j]);
}
}
}
for(int len=;len<qnt;len++)
ans=(ans+(ll)(qnt-len)*upt(g[len]-g[len-]))%mod;
}
void dfs(int cr)
{
if(col[cr]&&!vis[cr])solve(cr); ins[cr]=;//not use vis again
for(int i=hd[cr],v;i;i=nxt[i])
if(!ins[v=to[i]])
{
if(col[cr]!=col[v]||!col[cr])
//col!= not !col||!col//also !col
ans=(ans+(ll)bin[siz[v]]*bin[n-siz[v]])%mod;
dfs(v);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=,u,v;i<=m;i++)
scanf("%d%d",&u,&v),add(u,v),add(v,u);
bin[]=;for(int i=;i<=n;i++)bin[i]=upt(bin[i-]<<);
for(int i=;i<=n;i++)bin[i]=upt(bin[i]-);//
tarjan(,); dfs();
ans=(ll)ans*pw(bin[n]+,mod-)%mod;
printf("%d\n",ans);
return ;
}