[luoguP2495] [SDOI2011]消耗战（DP + 虚树）

传送门

明显虚树。

别的题解里都是这样说的。

先不考虑虚树，假设只有一组询问，该如何dp？

f[u]表示把子树u中所有的有资源的节点都切掉的最优解

如果节点u需要切掉了话，$f[u]=val[u]$

否则如果u的子树中有需要切除的点的话，$f[u] = min(val[u], \sum\limits_f[v])$

val[u]表示是根到u的路径上最小的边的权值。

最后转移到虚树上即可。

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 1000000#define LL long longusing namespace std;int n, m, cnt, rp, top, T;int head[N], to[N], nex[N], dfn[N], f[N][21], q[N], deep[N], s[N];LL ans[N], dp[N], val[N];bool flag[N];inline int read()inline void add(int x, int y, int z)inline void dfs1(int u)}head[u] = 1;}inline int calc_lca(int x, int y)inline bool cmp(int x, int y)inline void dfs2(int u)if(sum && !flag[u]) ans[u] = min(ans[u], sum);head[u] = 1;}inline void solve()lca = calc_lca(q[i], s[top]);while(dfn[lca] < dfn[s[top]])add(s[top  1], s[top], 0), top;}s[++top] = q[i];}while(top > 1) add(s[top  1], s[top], 0), top;dfs2(s[1]);printf("%lld\n", ans[s[1]]);for(i = 1; i <= m; i++) flag[q[i]] = 0;}int main()dp[1] = 1ll * 1e9 * 1e9;dfs1(1);T = read();while(T) solve();return 0;}

上一篇：[luoguP1129] [ZJOI2007]矩阵游戏（二分图最大匹配）

下一篇：[luoguP3953] 逛公园（DP + spfa）