【LOJ】【树形DP】2485 「CEOI2017」Chase_综合

LOJ 2485 「CEOI2017」Chase

题目大意

◇题目传送门◆

~~似乎压缩起来有点困难，所以就不压缩了吧 QwQ…~~

分析

考虑扔一个磁铁能够产生的让逃亡者和追逐者之间的差异。

这个差异就是这个节点的所有儿子的点权之和（因为父亲和它的贡献已经被计算过一次了）。

不难设状态 $f (u, i)$ 为在以 $u$ 为根的子树上的某个节点出发，扔 $i$ 个磁铁，最终停留在 $u$ 能够产生的最大贡献。另设 $v_u$ 为与 $u$ 相邻的点的点权和， $a_u$ 为 $u$ 的点权。

不难列出状态转移方程：

$f(u,i)=max?v∈son(u){f(v,i),f(v,i?1)+vu?av}f(u,i)=\max_{v\in son(u)}\{f(v,i),f(v,i-1)+v_u-a_v\}$

$f (u, i)$ 的初值为 $vu(i≠0),0(i=0)v_u(i\neq 0),0(i=0)$ 。

由于根不固定，所以我们考虑换根。

设 $g (u, i)$ 为从节点 $u$ 向子树内走，扔下 $i$ 个磁铁所能够产生的最大贡献。

转移显然可以写成（其中 $w$ 是 $u$ 的父亲）

$g(u,i)=max?v∈son(u){g(v,i),g(v,i?1)+vu?aw}g(u,i)=\max_{v\in son(u)}\{g(v,i),g(v,i-1)+v_u-a_w\}$

但是我们必须去重（有可能 $f, g$ 的路径都选到了同一个儿子），所以我们在更新 $f, g$ 开始前就更新答案，即先做：
$ans=\max_{i=1}^{V}\{f(u,i)+g(u,V-i)\}$

再对 $f, g$ 进行转移。

考虑对于 $u$ 子树中的两个节点 $v, w$ ，一种情况是从 $v$ 走上 $u$ 再走下 $w$ ，另一种情况是从 $w$ 走上 $u$ 再走下 $v$ ，这两种情况得到的答案是很有可能不一样的。

而在我们刚才的转移中，由于为了防止路径重复先更新了答案，这表明我们所得到的 $f$ 选取的路径一定是在 $g$ 选取的路径的左边。也就是说我们必须统计 $g$ 在 $f$ 左边的情况。

一种比较有效的方法是将 $v$ 压进一个栈里，再从栈中取出，一个个更新即可。

注意答案还需和 $max?(f(u,V),g(u,V))\max(f(u,V),g(u,V))$ 进行比较

参考代码

#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;typedef long long ll;
const int Maxn = 1e5;
const int Maxv = 100;int N, V;
int A[Maxn + 5];
vector<int> G[Maxn + 5];
void addedge(int u, int v) {
    G[u].push_back(v);G[v].push_back(u);
}ll val[Maxn + 5]; 
ll f1[Maxn + 5][Maxv + 5], f2[Maxn + 5][Maxv + 5];
ll ans;
void calc(int x, int y, int z) {
    for(int i = 1; i <= V; i++)ans = max(ans, f1[x][i] + f2[y][V - i]);for(int i = 1; i <= V; i++) {
    f1[x][i] = max(f1[x][i], max(f1[y][i], f1[y][i - 1] + val[x] - A[y]));f2[x][i] = max(f2[x][i], max(f2[y][i], f2[y][i - 1] + val[x] - A[z]));}
}
void DFS(int u, int fa) {
    for(int i = 1; i <= V; i++)f1[u][i] = val[u], f2[u][i] = val[u] - A[fa];for(int i = 0; i < (int)G[u].size(); i++) {
    int v = G[u][i];if(v == fa) continue;DFS(v, u);calc(u, v, fa);}stack<int> stk;for(int i = 1; i <= V; i++)f1[u][i] = val[u], f2[u][i] = val[u] - A[fa];for(int i = 0; i < (int)G[u].size(); i++){
    int v = G[u][i];if(v == fa) continue;stk.push(v);}while(!stk.empty()) {
    int v = stk.top();stk.pop(), calc(u, v, fa);}ans = max(ans, max(f1[u][V], f2[u][V]));
}int main() {
    
#ifdef LOACLfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifscanf("%d %d", &N, &V);for(int i = 1; i <= N; i++)scanf("%d", &A[i]);for(int i = 1; i < N; i++) {
    int u, v;scanf("%d %d", &u, &v);addedge(u, v);val[u] += A[v], val[v] += A[u];}DFS(1, 0);printf("%lld\n", ans);return 0;
}