求助,55pts(玄关)
查看原帖
求助,55pts(玄关)
895690
gghack_Nythix楼主2024/7/19 11:36

根本不知道怎么改了、

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
const int MAXX = 5e5 + 5;
const int mod = 1e9 + 7;
int low[MAXX],dfn[MAXX],cur,bridge[MAXX],bel[MAXX],bk,edccsz[MAXX],dp[MAXX][2],subsz[MAXX],ans;
struct node {
	int nxt,u,v;
}e[2000005],e2[2000005];
int b,head[2000005],km[2000005],head2[2000005],b2;
int ksm(int a,int b) {return km[b];}
void add(int u,int v){e[b] = {head[u],u,v},head[u] = b,++b;}
void newadd(int u,int v){e2[b2] = {head2[u],u,v},head2[u] = b2,++b2;}
void tarjan(int now,int from) {
	low[now] = dfn[now] = ++cur;
	for(int i = head[now]; ~i ; i = e[i].nxt) {
		int x = e[i].v;
		if(!dfn[x]) {
			tarjan(x,i);
			low[now] = min(low[now],low[x]);
			if(low[x] > dfn[now])bridge[i] = bridge[i ^ 1] = 1;
		}
		else if(i != (from ^ 1)) low[now] = min(low[now],dfn[x]);
	}
	return ;
}
void Ilovezisyh(int now,int pre,int current) {
	bel[now] = current;
	edccsz[current]++;
	for(int i = head[now]; ~ i;i = e[i].nxt) {
		if(bel[e[i].v] || bridge[i]) continue;
		Ilovezisyh(e[i].v,i,current);
	}
	return ;
}
void dp_TMLY(int now,int fa) {
	subsz[now] = 1;
	dp[now][0] = 1,dp[now][1] = ksm(2,edccsz[now]) - 1;
	for(int i = head2[now]; ~ i;i = e2[i].nxt) {
		int x = e2[i].v;
		if(x == fa) continue;
		dp_TMLY(x,now);
		subsz[now] += subsz[x];
		int dpnone = 0ll,dpedge = 0ll;
		dpnone = ((dp[now][0] % mod * dp[x][0] % mod) % mod * 2LL) % mod;
		dpedge = ((dp[now][1] % mod * dp[x][0] % mod) % mod * 2LL) % mod;
		dpedge = (dpedge + (dp[now][1] % mod * dp[x][1] % mod) % mod) % mod;
		dpedge = (dpedge + (dp[now][0] % mod * dp[x][1] % mod) % mod) % mod;
		dp[now][0] = dpnone,dp[now][1] = dpedge;
	}
	int totalsize = subsz[now];
	if(now == 1) totalsize --;
	ans = (ans + (dp[now][1] * ksm(2,m - totalsize) % mod)) % mod;
	//2^{m-totalsize}指的是定义范围外的我们随便选。
}
signed main(){
	cin >> n >> m;
	memset(head,-1,sizeof(head)); 
	memset(head2,-1,sizeof(head2));
	for(int i = 1;i <= m;++i) {
		int u,v;
		cin >> u >> v;
		add(u,v),add(v,u);
	}
	for(int i = 1;i <= n;++i) if(!dfn[i]) tarjan(i,-1);
	for(int i = 1;i <= n;++i) if(!bel[i]) ++bk,Ilovezisyh(i,-1,bk);
	for(int i = 0;i <= b;++i) {
		if(bel[e[i].u] != bel[e[i].v]) {
			newadd(bel[e[i].u],bel[e[i].v]);
		}
	} 
	km[0] = 1;
	for(int i = 1;i < 1000005;++i) km[i] = (km[i - 1] << 1) % mod; 
	dp_TMLY(1,0);
	cout << ans % mod << '\n';
	return 0;	
}
//割边会导致两点无法到达,跑一遍tarjan求出割边
//双连通分量中随便搞都不会导致其废掉
//这样就变成了树上dp
//dp[x][0]子树完全不射
//dp[x][1]子树有并且全部被保护
2024/7/19 11:36
加载中...