洛谷不支持邻项调整，如何把一道紫题降成蓝题呢？

首先想办法把他降成黄题

然后再升到蓝题

80 分做法

• 存边的数组开小了导致 RE

• 存点的数组开大了导致 MLE

满分做法

首先一个边双内部的边选不选都行。但是若桥不选，则桥两边只能有一边建造军营。

所以我们先把边双连通分量缩成一个点，缩完点之后变成一棵树，使用树形 DP。

这里的状态设计很重要。我使用 $dp_u$ 表示以 $u$ 为根的子树中选了军营的方案数。选 $u$ 和不选 $u$ 无所谓，因为只要子树中有被选的，对他的父亲来说是一样的。

然后考虑如何转移。首先初始值 $dp_u=2^{sum_u}$，$sum_u$ 表示边双中点的个数。

然后从 $v$ 转移到 $u$ 时，子树 $v$ 有选和不选两种情况。如果选了子树 $v$，那就是 $dp_v$。如果不选，那下边的 $siz_v$ 条树边可以随便选，就是 $2^{siz_v}$。

然后根据 DP 状态，最后要减去子树 $u$ 中一个也不选的情况，就是 $2^{siz_u-1}$。因为一个点也不选，树边可以随便选。

最后统计答案。首先加上 $dp_1$。然后发现小样例输出 $4$。因为还有别的情况，可能会只选了某个子树 $u$ 中的点，外面的点一个也不选，但外面选了某些边。所以就是 $dp_u\times fac_{cnt-siz_u-1}$。其中 $cnt$ 表示边双的个数。外面一共有 $m-siz_u$ 条边。这里减一的原因是 $u$ 到他父亲 $fa$ 的边 是一定不选的，选这条边造成的贡献已经在 $dp_{fa}$ 中算过一次了。

预处理 $2$ 的幂，时间复杂度为 $\mathcal O(n+m)$。

代码

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e^'0');
		e=getchar();
	}
	return x*y;
}
const int mod=1000000007,N=500005,M=1000005;
int n,m,ans;
int head[N],ver[M<<1],nxt[M<<1],idx=-1;
void add(int x,int y) {
	ver[++idx]=y,nxt[idx]=head[x],head[x]=idx;
}
vector<int>G[N];
int dfn[N],low[N],times,bel[N],cnt,sum[N];
bool bridge[M<<1];
void Tarjan(int u,int f) {
	dfn[u]=low[u]=++times;
	for(int i=head[u]; ~i; i=nxt[i]) {
		int v=ver[i];
		if(!dfn[v]) {
			Tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u]) bridge[i]=bridge[i^1]=1;
		} else if(v!=f) low[u]=min(low[u],dfn[v]);
	}
}
void dfs(int u) {
	bel[u]=cnt,++sum[cnt];
	for(int i=head[u]; ~i; i=nxt[i]) {
		int v=ver[i];
		if(bridge[i]||bel[v])continue;
		dfs(v);
	}
}
int dp[N],siz[N],fac[2000005];
bool vis[N];
void DP(int u) {
	vis[u]=1,siz[u]=1,dp[u]=fac[sum[u]];
	for(auto v:G[u]) {
		if(vis[v])continue;
		DP(v);
		dp[u]=(dp[v]+fac[siz[v]])%mod*dp[u]%mod;
		siz[u]+=siz[v];
	}
	dp[u]=(dp[u]-fac[siz[u]-1]+mod)%mod;
}
signed main() {
	memset(head,-1,sizeof head);
	R(n),R(m);
	for(int i=1; i<=m; ++i) {
		int R(x),R(y);
		add(x,y),add(y,x);
	}
	Tarjan(1,-1);
	for(int i=1; i<=n; ++i) {
		if(!bel[i]) {
			++cnt;
			dfs(i);
		}
	}
	for(int u=1; u<=n; ++u) {
		for(int i=head[u]; ~i; i=nxt[i]) {
			int v=ver[i];
			if(bel[u]!=bel[v]) G[bel[u]].push_back(bel[v]);
		}
	}
	fac[0]=1;
	for(int i=1; i<=2000000; ++i) fac[i]=fac[i-1]*2%mod;
	DP(1);
	ans=dp[1];
	for(int i=2; i<=cnt; ++i) {
		ans=(ans+dp[i]*(fac[cnt-siz[i]-1])%mod)%mod;
	}
	cout<<ans*fac[m-cnt+1]%mod;
	return 0;
}

极下位紫，但是我场上dp式子推错了。

$0$ 分做法

这个做法有很多种，例如删掉freopen，我讲一讲我自己的做法吧

首先看到这个题是使用tarjan找边双连通分量，然后缩点，这样就缩成一棵树了

为什么要缩点呢？因为我们注意到敌人只会炸掉一条道路，如果炸毁的这条路是一条割边，那一定会将一个图分成两部分，如果这两部分分别有一个军营，那么这种情况就不合法

但是我们发现如果一个图里面没有割边，也就是边双连通分量，敌人随便炸，都不会将图分成两部分，更不会将军营分成两部分了

我们缩完点之后，会发现这个图变成了一棵树，树边全是割边

首先我们对于每一个缩完点之后的点 $i$ 预处理出来两个东西：$V_i$ 和 $E_i$

$V_i$ 表示这个边双里面有多少个点， $E_i$ 表示这个边双里面有多少个边

然后统计答案，发现是数数题，所以只能使用dp

设 $dp_{u,0/1}$ 表示在 $u$ 这个子树内有/没有节点建造了军营

首先考虑 $dp_{u,0}$ 的转移：

对于任意两个点 $u$ 和 $v$ ，我们用一个二进制数表示，第一个数表示 $u$ 选不选，第二个数表示 $(u,v)$ 选不选，第三个数表示 $v$ 选不选

仅有：000和010两种情况

对于 $dp_{u,1}$ 的转移：

仅有：001、011、100、110、111这五种情况、

However，如果我们的图是一个长度为 $3$ 的链，那我们不能保证算出来正确答案，因为可能有下面这一种情况：11001，这种情况是不合法的

所以这种做法是错误的，没有保证 $v$ 子树内与 $u$ 的连通性

好，以上都是扯淡

$100$ 分做法

首先tarjan缩点显然，dp状态需要修改

设 $dp_{u,0/1}$ 表示对于一个节点 $u$ ，其子树内有/没有点建造军营，并且保证如果 $u$ 子树内有点建造军营，那么它一定和 $u$ 联通，并且保证 $u$ 以外子树内没有人选

则有转移：

$$dp_{u,0}=dp_{u,0}\times dp_{v,0}\times 2$$

对于 $dp_{u,1}$ ，我们考虑每次向 $u$ 的子树内添加一个子树，分为下面两种情况

1. $u$ 子树内已经有人选了
   • 可能 $v$ 中没人选，$(u,v)$ 就选不选无所谓
   • 可能 $v$ 中有人选，$(u,v)$ 必须选

则有转移：

$$dp_{u,1}=dp_{u,1}\times(dp_{v,0}\times 2+dp_{v,1}) $$

2. $u$ 子树内还没人选
   • 直接算就行

则有转移：

$$dp_{u,1}=dp_{u,1}+dp_{u,0}\times dp_{v,1}$$

然后我们统计答案，我们设 $sum_u$ 表示以 $u$ 为根其子树内一共有多少条边，分为下面两种情况：

1. $u=1$ 直接 $ans+dp_{u,1}$
2. $u \ne 1$ ，这时候的 $dp_{u,1}$ 仅仅表示在 $u$ 子树内选的东西，不包含 $u$ 子树外的，所以 $ans+dp_{u,1}\times 2^{sum_1-sum_u-1}$ 这里 $-1$ 自己退一下就好

初值：$dp_{u,0}=2^{E_u}$ 和 $dp_{u,1}=2^{E_u+V_u}-dp_{u,0}$

#include<iostream>
#include<cstdio>
#include<vector>
#define int long long
using namespace std;
bool Test_MLE_start;
constexpr int N=5*1e5+10,M=1e6+10,mod=1e9+7;
int _=1,n,m,tot=1,num=0,dcc=0,ans=0,head[N],dfn[N],low[N],c[N],V[N],E[N],sum[N],dp[N][2];
vector<int> G[N];bool br[M<<1];
struct edge{int v,nxt;}a[M<<1];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}
inline void files(){
	freopen("barrack.in","r",stdin);
	freopen("barrack.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
void add(int u,int v){
	a[++tot].v=v;
	a[tot].nxt=head[u];
	head[u]=tot;
}
void tarjan(int u,int ine){
	dfn[u]=low[u]=++num;
	for(int i=head[u];i;i=a[i].nxt){
		int v=a[i].v;
		if(!dfn[v]){
			tarjan(v,i);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u]) br[i]=br[i^1]=1;
		}else if(i!=(ine^1)) low[u]=min(low[u],dfn[v]);
	}
}
void dianfengshan(int u){
	c[u]=dcc;V[dcc]++;
	for(int i=head[u];i;i=a[i].nxt){
		int v=a[i].v;
		if(c[v]||br[i]) continue;
		dianfengshan(v);
	}
}
int ksm(int a,int b){
	int ans=1;
	for(;b;b>>=1){
		if(b&1) ans=ans*a%mod;
		a=a*a%mod;
	}return ans;
}
void dfs2(int u,int dad){
	for(auto v:G[u]){
		if(v==dad) continue;
		dfs2(v,u);sum[u]=(sum[u]+sum[v]+1)%mod;
	}
}
void dfs(int u,int dad){
	for(auto v:G[u]){
		if(v==dad) continue;dfs(v,u);
		dp[u][1]=(dp[u][1]*(dp[v][0]*2+dp[v][1])%mod+dp[u][0]*dp[v][1]%mod)%mod;
		dp[u][0]=(dp[u][0]*dp[v][0]*2)%mod;
	}
	if(u==1) ans=(ans+dp[u][1])%mod;
	else ans=(ans+ksm(2,sum[1]-sum[u]-1)*dp[u][1]%mod)%mod;
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),m=reads();
		for(int i=1;i<=m;i++){
			int u=reads(),v=reads();
			add(u,v),add(v,u);
		}for(int i=1;i<=n;i++){
			if(!dfn[i]) tarjan(i,0);
		}for(int i=1;i<=n;i++){
			if(!c[i]) dcc++,dianfengshan(i);
		}for(int i=2;i<=tot;i++){
			int u=a[i^1].v,v=a[i].v;
			if(c[u]==c[v]){
				E[c[u]]++;
				continue;
			}G[c[u]].push_back(c[v]);
		}for(int i=1;i<=dcc;i++){
			E[i]>>=1,sum[i]=E[i];
			dp[i][0]=ksm(2,E[i]);
			dp[i][1]=(ksm(2,E[i]+V[i])-dp[i][0]+mod)%mod;
		}dfs2(1,0);dfs(1,0);
		printf("%lld\n",ans); 
	}
	return 0;
}

嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟嘟