传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3836
【题解】
这题非常的妙啊！以下参考Sengxian：https://blog.sengxian.com/solutions/bzoj-3836
首先有这么一个性质：最长链不超过10。
也就是，任选点为根，dfs下去，最多不超过10层。
这有什么用呢？这提示我们，状压！
下面用一道经典题来引入这个很妙的dp：
====================================分割线==========================================
【例】
给出一棵$n$个点的树，每个点有体积$v_i$和价值$w_i$。求树上的一个连通块，使得体积不超过$m$，价值最大。
$1 leq n, m v_ileq 10^3, 0 leq w_i leq 10^9$
【分析】
这题有多种做法，如果直接背包合并，复杂度是$O(nm^2)$，难以承受。
其中一种改进方法是在DFS序上做，那么每次要么跳过一段子树，要么继续往下，复杂度$O(nm)$，这也是经典trick。
还有一个trick是zzy7在校内训练提出的方法，跟要讲的这题有异曲同工之妙，在这里感谢zzy7（虽然可能已经AFO了）
我们考虑正常背包合并，复杂度之所以为$O(nm^2)$，因为每次要合并背包。
是否可以在做的时候，把父亲的dp值传递给儿子，然后由儿子继续父亲的dp，然后做下去呢？答案是可以的。
我们修改表示方式为做完了上面那条链和下面的子树的答案，每次做两件事情：把父亲的传给儿子做，把儿子做完的传上来。
复杂度同样是$O(nm)$。
====================================分割线==========================================
我们考虑对原题有什么帮助？答案是肯定的！
考虑$f_{x,s}$表示到$x$点，$x$以上的链（包括$x$），状态是$s$（3进制，0表示选择了，1表示没选且没被覆盖，2表示没选但被覆盖了，这里的状态记录的是父亲一直到根这条链上的，所以是$3^{10}$的。）
那么我们先把父亲的dp值传给儿子。这里具体传的时候，就可以考虑儿子的选择了。
分两类：
1. 不选儿子：那么如果儿子被覆盖，儿子二进制位改变为2；否则改为1（结合上面的定义）
2. 选儿子：把所有跟儿子相连的父亲，如果为1的改为2，加入选儿子的代价。
考虑儿子的dp值传给父亲。
那么要么是对应传送（儿子的s传给父亲的s），要么，因为儿子这个点不在父亲的状态表示了，所以儿子这个点也可以选择二进制位为2。
具体可以看代码理解。复杂度$O(3^{10}n)$。
（自己强制看成树把读入的边数量打成$n-1$也是没谁了）
# include <vector> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int N = 20005, M = 60005, K = 12; const int mod = 1e9+7; const int inf = 1e9; int n, m, c[N], bin[K]; vector<int> G[N]; bool vis[N]; int ans = 0, f[K][M]; # define bit(x, i) (((x) / bin[i]) % 3) inline void cmin(int &x, const int &y) { if(x > y) x = y; } // the trick that zzy7 gives us int dep[N]; bool vd[K]; inline void dfs(int x, int d) { vis[x] = 1; dep[x] = d; fill(f[dep[x]], f[dep[x]] + bin[10], inf); if(dep[x] == 0) { f[0][0] = c[x]; f[0][1] = 0; f[0][2] = inf; } else { memset(vd, 0, sizeof vd); for (int i=0; i<G[x].size(); ++i) if(vis[G[x][i]]) vd[dep[G[x][i]]] = 1; for (int sta = 0; sta < bin[dep[x]]; ++ sta) { if(f[dep[x]-1][sta] == inf) continue; int nsta = 0; bool hv = 0; for (int i=0; i<dep[x]; ++i) { if(vd[i] && bit(sta, i) == 0) hv = 1; if(vd[i] && bit(sta, i) == 1) nsta += bin[i]; } // not choose if(hv) cmin(f[dep[x]][sta + bin[dep[x]] * 2], f[dep[x]-1][sta]); else cmin(f[dep[x]][sta + bin[dep[x]]], f[dep[x]-1][sta]); // choose cmin(f[dep[x]][sta + nsta], f[dep[x]-1][sta] + c[x]); } } for (int i=0; i<G[x].size(); ++i) if(!vis[G[x][i]]) { dfs(G[x][i], d+1); for (int sta=0; sta < bin[dep[x]+1]; ++sta) f[dep[x]][sta] = min(f[dep[x]+1][sta], f[dep[x]+1][sta + bin[dep[x]+1] * 2]); } } inline void solve(int x) { dfs(x, 0); ans += min(f[0][0], f[0][2]); } int main() { cin >> n >> m; bin[0] = 1; for (int i=1; i<=10; ++i) bin[i] = bin[i-1] * 3; for (int i=1; i<=n; ++i) scanf("%d", c+i); for (int i=1, u, v; i<=m; ++i) { scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } for (int i=1; i<=n; ++i) if(!vis[i]) solve(i); cout << ans; return 0; }