同志们下列代码下发样例4通过不了,但是AC了
什么情况qwq
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5e5+5,maxm=1e6+5,p=1e9+7;
int ksm(int x,int y){
int r=1;
while(y){
if(y&1){
r=r*x%p;
}
x=x*x%p;
y>>=1;
}
return r;
}
struct linestar{
signed cnt=0,head[maxm<<1],to[maxm<<1],last[maxn];
void add(int x,int y){
head[++cnt]=last[x];
last[x]=cnt;
to[cnt]=y;
}
}edg;
int n,m,root;
struct tarjan{
signed cnt,tot,low[maxn],dfn[maxn],note[maxn],E[maxn],U[maxn],s[maxn];
bool ins[maxn];
stack<int> st;
vector<signed> v[maxn];
int dp[maxn][2];
void dfs(int x,int fa){
low[x]=dfn[x]=++tot;
st.push(x);
ins[x]=true;
for(int i=edg.last[x];i;i=edg.head[i]){
int to=edg.to[i];
if(to==fa){
continue;
}
if(!dfn[to]){
dfs(to,x);
low[x]=min(low[x],low[to]);
}
else if(ins[to]){
low[x]=min(low[x],dfn[to]);
}
}
if(low[x]==dfn[x]){
cnt++;
int i;
do{
i=st.top();
ins[i]=false;
note[i]=cnt;
E[cnt]++;
st.pop();
}while(x^i);
}
}
void check(){
for(int i=1;i<=n;i++){
for(int j=edg.last[i];j;j=edg.head[j]){
int to=edg.to[j];
if(note[to]^note[i]){
v[note[i]].push_back(note[to]);
}
else{
U[note[i]]++;
}
}
}
for(int i=1;i<=cnt;i++){
U[i]>>=1;
dp[i][0]=ksm(2,U[i]);
dp[i][1]=(ksm(2,U[i]+E[i])-dp[i][0])%p+p;
dp[i][1]%=p;
}
}
void cals(int x,int fa){
// cout<<x<<'\n';
s[x]=U[x];
for(auto t:v[x]){
if(t^fa){
cals(t,x);
s[x]+=s[t]+1;
}
}
}
int ans=0;
void solve(int x,int fa){
for(int to:v[x]){
if(to^fa){
solve(to,x);
dp[x][1]=dp[x][0]*dp[to][1]%p+dp[x][1]*(2*dp[to][0]+dp[to][1])%p;
dp[x][1]%=p;
dp[x][0]=2*dp[to][0]*dp[x][0]%p;
}
}
if(x==1){
ans+=dp[x][1];
ans%=p;
}
else{
ans+=ksm(2,s[1]-s[x]-1)*dp[x][1]%p;
ans%=p;
}
}
}tar;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
edg.add(x,y);
edg.add(y,x);
}
tar.dfs(1,0);
tar.check();
tar.cals(1,0);
tar.solve(1,0);
cout<<tar.ans;
}