样例不过求调(玄关)
查看原帖
样例不过求调(玄关)
1004026
__Charlie_Chen__楼主2024/8/26 19:08
#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int mod=1e9+7;
const int maxn=5e5+10,maxm=1e6+10;
struct node {
	int u,v,nxt;
} e[maxm*2],e2[maxm*2];
int h[maxn],dfn[maxn],low[maxn],bel[maxn],d[maxn];
int h2[maxn],tot2,num[maxn],siz[maxn],dp[maxn][2];
int n,m,tot,idx,cnt,ans;
stack<int>st;

inline int r(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}

void add(int u,int v){
	e[tot].u=u;
	e[tot].v=v;
	e[tot].nxt=h[u];
	h[u]=tot++;
}

void ADD(int u,int v){
	e2[tot2].u=u;
	e2[tot2].v=v;
	e2[tot2].nxt=h2[u];
	h2[u]=tot2++;
}

ll qpow(ll a,int b){
	ll res=1;
	while(b){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

void tarjan(int u,int fa){
	dfn[u]=low[u]=++idx;
	st.push(u);
	for(int i=h[u];i!=-1;i=e[i].nxt){
		int v=e[i].v;
		if(!dfn[v]){
			tarjan(v,i);
			low[u]=min(low[u],low[v]);
		}else if(i!=(fa^1)) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		bel[u]=++cnt;
		num[cnt]++;
		while(!st.empty()&&st.top()!=u){
			int v=st.top();
			st.pop();
			bel[v]=cnt;
			num[cnt]++;
		}
		st.pop();
	}
}

void dfs(int u,int fa){
	siz[u]=d[u];
	for(int i=h2[u];i!=-1;i=e2[i].nxt){
		int v=e2[i].v;
		if(v==fa) continue;
		dfs(v,u);
		siz[u]+=(1+siz[v]);
	}
}

void DP(int u,int fa){
	for(int i=h2[u];i!=-1;i=e2[i].nxt){
		int v=e2[i].v;
		if(v==fa) continue;
		DP(v,u);
		dp[u][1]=(dp[u][1]*(((dp[v][0]<<1)+dp[v][1])%mod)%mod+dp[u][0]*dp[v][1]%mod+mod)%mod;
		dp[u][0]=dp[u][0]*((dp[v][0]<<1)%mod)%mod;
	}
	if(u==1) ans=(ans+dp[1][1])%mod;
	else ans=(ans+dp[u][1]*qpow(2,siz[1]-siz[u]-1))%mod;
}

int main(){
	memset(h,-1,sizeof(h));
	memset(h2,-1,sizeof(h2));
	n=r(),m=r();
	for(int i=1,u,v;i<=m;i++){
		u=r(),v=r();
		add(u,v),add(v,u);
	}
	tarjan(1,0);
	for(int i=2;i<=2*m+1;i+=2){
		int u=e[i].u,v=e[i].v;
		if(bel[u]!=bel[v]){
			ADD(bel[u],bel[v]);
			ADD(bel[v],bel[u]);
		}else d[bel[u]]++;
	}
	for(int i=1;i<=cnt;i++){
		dp[i][0]=qpow(2,d[i]);
		dp[i][1]=qpow(2,d[i]+num[i])-dp[i][0];
	}
	dfs(1,0);
	DP(1,0);
	printf("%d\n",ans);
	return 0;
}

样例一的输出为 1
样例二输出为 92

2024/8/26 19:08
加载中...