Description
我的灵魂与我之间的距离如此遥远，而我的存在却如此真实。
——加缪《局外人》
我醒来的时候，发现满天星斗照在我的脸上。田野上的声音一直传到我的耳畔。夜的气味，土地的气味，海盐的气味，使我的两鬓感到清凉。这沉睡的夏夜的奇妙安静，像潮水一般浸透我的全身。这时，长夜将尽，汽笛叫了起来。它宣告有些人踏上旅途，要去一个从此和我无关痛痒的世界。
这时我在想一个问题：我有一个n个点，m条边的无向图，第i个点建立一个旅游站点的费用是c_i。特别地，这张图中的任意两点间不存在节点数超过10的简单路径。
为了把一切都做得完善，为了使我感到不那么孤独，我想要建造一些旅游站点使得每个点要么建立了旅游站点，要么与它有边直接相连的点里至少有一个点建立了旅游站点。我还希望这个建造方案总花费尽量少。
请求出这个花费。
对于100%的测试点，满足1<=n<=2*10^4,0<=m<=2.5*10^4,0<=c_i<=10^4。
Solution
不存在节点数超过10的简单路径，那就是说DFS树最多只有10层
可以在DFS树上进行树形DP
但是祖先的状态会对自己造成影响。
考虑状压
因为祖先只有10个，用三进制表示，0/1/2表示没选也没覆盖，没选但覆盖，选了
第K位表示深度为K的祖先的状态，根的深度为0
按照欧拉序DP
在访问这个点的子树之前，先将父亲的状态继承下来。
枚举状态S
分这个点选和不选两种情况讨论，
不选的话看它会不会被返祖边上覆盖。
选的话看它能不能覆盖某些祖先
相应的修改状态
即
相当于是欧拉序的入点
然后访问k的子树，对于某一棵子树，它继承完以后返回并重新计算F[k]，将返回后的答案继续让下一棵子树继承。
相当于欧拉序的出点
复杂度。。。
理论最坏是
然而它能过。。。
Code
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <cmath>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define N 30005
using namespace std;
int dep[N],n,m,fs[N],c[N],nt[2*N],dt[2*N],ans,m1,cf[11],f[11][60000],d[N],ms[11][60000];
bool bz[N];
inline void update(int &x,int y)
{
if(y<x) x=y;
}
void dfs(int k,int fa)
{
bz[k]=1;
dep[k]=dep[fa]+1;
int v=0;
d[0]=0;
for(int i=fs[k];i;i=nt[i])
{
int p=dt[i];
if(bz[p]) d[++d[0]]=dep[p];
}
fo(i,0,cf[dep[k]+1]-1) f[dep[k]][i]=1802201963;
if(dep[k]!=0)
fo(s,0,cf[dep[k]]-1)
{
int q=0,qs=0;
fo(i,1,d[0])
{
int v=ms[d[i]][s];
if(v==2) q=1;
if(v==0) qs+=cf[d[i]];
}
update(f[dep[k]][s+q*cf[dep[k]]],f[dep[fa]][s]);
update(f[dep[k]][s+2*cf[dep[k]]+qs],f[dep[fa]][s]+c[k]);
}
else f[dep[k]][0]=0,f[dep[k]][1]=1802201963,f[dep[k]][2]=c[k];
for(int i=fs[k];i;i=nt[i])
{
int p=dt[i];
if(!bz[p])
{
dfs(p,k);
fo(s,0,cf[dep[k]]-1)
{
fo(x,0,2)
{
int v1=f[dep[p]][s+x*cf[dep[k]]+cf[dep[p]]],v2=f[dep[p]][s+x*cf[dep[k]]+2*cf[dep[p]]];
f[dep[k]][s+x*cf[dep[k]]]=(v1<v2)?v1:v2;
}
}
}
}
}
void link(int x,int y)
{
nt[++m1]=fs[x];
dt[fs[x]=m1]=y;
}
int main()
{
cin>>n>>m;
fo(i,1,n) scanf("%d",&c[i]);
cf[0]=1;
fo(i,1,10) cf[i]=cf[i-1]*3;
fo(i,1,m)
{
int x,y;
scanf("%d%d",&x,&y);
link(x,y);
link(y,x);
}
int ans=0;
dep[0]=-1;
fo(s,0,cf[10])
{
fo(i,0,10)
{
ms[i][s]=(s/cf[i])%3;
}
}
fo(i,1,n)
{
if(!bz[i]) dfs(i,0),ans+=min(f[0][1],f[0][2]);
}
printf("%d\n",ans);
}