rt,怀疑是 dp 的问题,只过了链的 10 分。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7;
int n,m,dep[500005],siz[500005],x,y,op[500005],kk[500005],cnt;
ll dp[500005][2],z[500005];
vector<int>q[500005],p[500005];
ll inline qpow(ll x,ll y){
ll ans=1;
while(y){
if(y&1)ans=(ans*x)%mod;
x=(x*x)%mod;
y>>=1;
}
return ans;
}
void inline dfs(int x,int y){
op[x]=1;
dep[x]=y;
for(int i=0;i<q[x].size();i++)
if(!op[q[x][i]])dfs(q[x][i],y+1),p[x].push_back(0);else if(dep[q[x][i]]!=dep[x]-1)p[x].push_back(1);else p[x].push_back(0);
}
void inline dfs2(int x,int y,int z){
op[x]=1;
for(int i=0;i<q[x].size();i++)if(!op[q[x][i]]){dfs2(q[x][i],x,i);siz[x]+=siz[q[x][i]];}
if(siz[x]==0&&y!=0)p[y][z]=1;
}
void inline dfs3(int x){
op[x]=1;kk[x]=cnt;
for(int i=0;i<q[x].size();i++)if((!op[q[x][i]])&&!(p[x][i]))dfs3(q[x][i]);
}
void inline dfs4(int x){
op[x]=1;
for(int i=0;i<q[x].size();i++)if(!op[q[x][i]]){dfs4(q[x][i]);
if(kk[x]==kk[q[x][i]])continue;
p[kk[x]].push_back(kk[q[x][i]]);
p[kk[q[x][i]]].push_back(kk[x]);}
}
void inline dfs5(int x){//use p
op[x]=1;
ll ans1=(qpow(2,z[x])-(ll)1+mod)%mod,ans4=(qpow(2,z[x])+mod)%mod;
ll ans2=1;
ll ans3=0;
vector<ll>ss,sss;
ss.clear();sss.clear();
for(int i=0;i<p[x].size();i++)
{
if(!op[p[x][i]])
{
dfs5(p[x][i]);
siz[x]+=siz[p[x][i]];
ans1=(ans1*((dp[p[x][i]][1]+qpow(2,siz[p[x][i]]))%mod))%mod;
ans4=(ans4*((dp[p[x][i]][1]+qpow(2,siz[p[x][i]]))%mod))%mod;
ans2=(ans2*((dp[p[x][i]][0]+qpow(2,siz[p[x][i]]))%mod))%mod;
ss.push_back(dp[p[x][i]][0]);
sss.push_back(siz[p[x][i]]);
}
}
siz[x]++;
if(ans2==1&&siz[x]==1){
dp[x][0]=dp[x][1]=ans1;return ;}
ans3=(ans3-qpow(2,siz[x]-1)+mod)%mod;
//dp[x][1]=(ans1+ans2+ans3)%mod;
for(int i=0;i<ss.size();i++)
ans3=(ans3+ss[i]*qpow(2,siz[x]-sss[i]-1)%mod)%mod;
//cout<<x<<" "<<ans1<<" "<<ans2<<" "<<ans3<<" "<<ans4<<endl;
dp[x][0]=(ans1+ans2+ans3)%mod;
dp[x][1]=(ans4-qpow(2,siz[x]-1)+mod)%mod;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>x>>y;
q[x].push_back(y);
q[y].push_back(x);
}
dfs(1,1);
for(int i=1;i<=n;i++)
for(int j=0;j<q[i].size();j++){
if(p[i][j])
if(dep[q[i][j]]>dep[i])
siz[q[i][j]]++,siz[i]--;
else
siz[q[i][j]]--,siz[i]++;}
memset(op,0,sizeof(op));
dfs2(1,0,0);
memset(op,0,sizeof(op));
for(int i=1;i<=n;i++){
if(!kk[i]){
cnt++;
dfs3(i);
}
}
memset(op,0,sizeof(op));
for(int i=1;i<=n;i++)
p[i].clear();
dfs4(1);
for(int i=1;i<=n;i++)
z[kk[i]]++;
memset(op,0,sizeof(op));
memset(siz,0,sizeof(siz));
dfs5(1);
cout<<(dp[1][0]*qpow(2,m-cnt+1))%mod<<endl;
}
qaq