Solution

这么喜欢卡常 /fn

显然求出一棵 DFS 树，深度不超过 $10$。在 DFS 树上进行树形 DP。

记录 $dp_{S}$ 表示当前 $u$ 和 $u$ 的所有祖先的状态：

• $0$ 表示当前节点没有放置关键点，且目前也没有相邻关键点；
• $1$ 表示当前节点放置了关键点；
• $2$ 表示当前节点没有放置关键点，且存在相邻关键点。

随着你的遍历，有两种操作：

1. 访问到儿子去。这时候枚举儿子节点有没有放置关键点即可。
2. 回溯。这时候要求儿子节点必须是状态 $1/2$。

可以做到 $O(3^{10}(n+m))$。

注意常数。以及图可能有多个连通块，需要依次累加。

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=20000+10,MAXM=60000+10;
int n,m,ans,c[MAXN],dep[MAXN],dp[MAXM],p3[MAXN];
vector<int> G[MAXN],T[MAXN],U[MAXN];
inline void dfs(const int u,const int f) {
	dep[u]=dep[f]+1;
	for(auto v:G[u]) {
		if(dep[v]) {
			if(dep[v]<dep[u]) U[u].push_back(v);
			continue ;	
		}
		dfs(v,u),T[u].push_back(v);
	}
	return ;
}
int w[15][MAXM];
inline void solve(const int u) {
	ffor(i,0,p3[dep[u]-1]-1) {
		int st=i;
		for(auto v:U[u]) if(w[dep[v]-1][st]==1) {st+=2*p3[dep[u]-1];break ;}
		dp[st]=min(dp[st],dp[i]); 
		st=i+p3[dep[u]-1];
		for(auto v:U[u]) if(w[dep[v]-1][st]==0) st+=2*p3[dep[v]-1];
		dp[st]=min(dp[st],dp[i]+c[u]);	
	}
	for(auto v:T[u]) solve(v);
	ffor(i,0,p3[dep[u]]-1) {
		if(i<p3[dep[u]-1]) {dp[i]=0x3f3f3f3f;continue ;}
		dp[i%p3[dep[u]-1]]=min(dp[i%p3[dep[u]-1]],dp[i]);
		if(i>p3[dep[u]-1]-1) dp[i]=0x3f3f3f3f;
	}
	return ;
}
vector<int> rt;
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m,memset(dp,0x3f,sizeof(dp)),p3[0]=1;
	ffor(i,1,10) p3[i]=p3[i-1]*3;
	ffor(i,0,p3[10]) ffor(j,0,10) w[j][i]=(i/p3[j])%3;	
	ffor(i,1,n) cin>>c[i];
	ffor(i,1,m) {int u,v;cin>>u>>v,G[u].push_back(v),G[v].push_back(u);}
	ffor(i,1,n) if(!dep[i]) rt.push_back(i),dfs(i,0);
	for(auto id:rt) dp[0]=0,solve(id),ans+=dp[0];
	cout<<ans;
	return 0;
}