【Codeforces】CF 1998 D

The Omnipotent Monster Killer

#树形dp #枚举

题目描述

You, the monster killer, want to kill a group of monsters. The monsters are on a tree with $n$ vertices. On vertex with number $i$ ($1\le i\le n$), there is a monster with $a_i$ attack points. You want to battle with monsters for $10^{100}$ rounds.

In each round, the following happens in order:

1. All living monsters attack you. Your health decreases by the sum of attack points of all living monsters.
2. You select some (possibly all or none) monsters and kill them. After being killed, the monster will not be able to do any attacks in the future.

There is a restriction: in one round, you cannot kill two monsters that are directly connected by an edge.

If you choose what monsters to attack optimally, what is the smallest health decrement you can have after all rounds?

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^4$). Description of the test cases follows.

The first line of each test case contains an integer $n$ ($1\le n\le 3\cdot 10^5$).

The second line of each test case contains $n$ integers $a_1,\dots ,a_n$ ($1\le a_i\le 10^{12}$).

The following $n-1$ lines each contain two integers $x,y$ ($1\le x,y\le n$), denoting an edge on the tree connecting vertex $x$ and $y$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot 10^5$.

输出格式

For each test case, print one integer: the minimum possible health decrement.

样例 #1

样例输入 #1

3
1
1000000000000
5
47 15 32 29 23
1 2
1 3
2 4
2 5
7
8 10 2 3 5 7 4
1 2
1 4
3 2
5 3
6 2
7 5

样例输出 #1

1000000000000
193
57

解题思路

首先对于点的删除，总共的次数不会很多，因为最差情况下也能选择树种一半的节点，然后删除大的那一部分，因此总共次数在$\lceil lo{g}_{2}n\rceil$次。

由于每个节点之间具有依赖关系，难以贪心，因此容易想到使用树形$dp$来具体选择什么时候删除哪些节点。

因此，我们可以设计状态$f_{u,i}$表示$u$节点在第$i$轮删除时，其子树的最小代价，有如下转移方程：

$$f_{u,i}=f_{u,i}+f_{v,j}(v\in so{n}_u\&\&j\ne i)$$

因为轮次只有$lo{g}_{2}n$种，因此我们可以暴力枚举所有的状态，从子树向根转移，最后的答案就是 ${\min }_{i=1}^{i\le lo{g}_{2}n}{f}_{1,i}$

代码

void solve() {int n;std::cin >> n;std::vector<int>a(n + 1);for (int i = 1; i <= n; ++i) {std::cin >> a[i];}std::vector<std::vector<int>> e(n + 1);for (int i = 1; i <= n - 1; ++i) {int u, v;std::cin >> u >> v;e[u].emplace_back(v);e[v].emplace_back(u);}std::vector<std::array<int,24>>f(n + 1);auto dfs = [&](auto&& self, int u, int fa)->void {for (int i = 1; i <= 23; ++i) {f[u][i] = i * a[u];}for (auto& v : e[u]) {if (v == fa) continue;self(self, v, u);for (int i = 1; i <= 23; ++i) {int minx = inf;for (int j = 1; j <= 23; ++j) {if (i == j) continue;minx = std::min(minx, f[v][j]);}f[u][i] += minx;}}};dfs(dfs, 1, -1);int res = *std::min_element(f[1].begin() + 1, f[1].end());std::cout << res << "\n";
}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;std::cin >> t;while (t--) {solve();}
};