Power Tree
简单题，场上大概写了 50min。
Sol.1 树形 DP
对所有数变 \(0\) 的条件进行刻画，把子树的条件画在序列上。具体而言，我们求出树的中序遍历，选择一个节点等价于将其子树的区间 \([l, r]\) 分离出来，即在 \(l - 1, l\) 之间与 \(r, r+1\) 之间加一个隔板。那么一个方案的叶子能变成 \(0\)，当且仅当同时满足下列两个条件：
- 每一段内不超过 \(1\) 个叶子。
- 每个叶子必须被覆盖过一次。
注意到如果一颗子树内已经存在一段有 \(\ge 2\) 个叶子，则往祖先方向走一定无法使得方案合法。因为祖先的区间一定是包含自己的区间的，因此隔板没有办法放在这颗子树内的区间。
由此可以得出一个结论：一颗子树内最多存在一个未被覆盖的节点。
由此可以设计 DP：\(dp_{i, 0/1}\) 表示在 \(i\) 的子树内，存在 \(0/1\) 个未被覆盖的节点的最小花费。转移即可：
- \(dp_{i, 0}\gets\min\{\sum dp_{v, 0}, dp_{j, 1} + a_i+\sum_{v\ne j}dp_{v, 0}\}\)。
- \(dp_{i, 1}\gets \min\{dp_{j, 1} + \sum_{v\ne j}dp_{v, 0}\}\)。
考虑构造方案。我们自顶向下构造，判断从某个状态能否推到后面的状态。如果可以，继续递归构造。如果直接这样模拟是 \(O(n^2)\) 的。但是你发现有很多次递归构造都是重复的，因此对每个节点递归构造的次数记录一下，记忆化搜索式地完成构造即可。
时间复杂度 \(O(n)\)。
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using pi = pair<int, int>;
typedef long long ll;
const int N = 200005;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n;
ll a[N];
vector<int> g[N];
ll dp[N][2], sm[N], ans;
bitset<N> res;
void dfs(int u, int fa)
{if(g[u].size() == 1 && fa != 0){dp[u][0] = a[u];dp[u][1] = 0;return;}ll tmp = 0;for(auto v : g[u]){if(v == fa) continue;dfs(v, u);tmp += dp[v][0];}sm[u] = tmp;dp[u][0] = min(dp[u][0], tmp);for(auto v : g[u]){if(v == fa) continue;dp[u][0] = min(dp[u][0], tmp - dp[v][0] + dp[v][1] + a[u]);dp[u][1] = min(dp[u][1], tmp - dp[v][0] + dp[v][1]);}
}
bitset<2> vis[N];
void dfs2(int u, int fa, int typ)
{if(vis[u][typ]) return;vis[u][typ] = 1;ll pans = dp[u][typ];if(g[u].size() == 1 && fa != 0){if(typ == 0) res[u] = 1;return;}if(typ == 0){if(sm[u] == pans){for(auto v : g[u]){if(v == fa) continue;dfs2(v, u, 0);}}int premx = -1, sufmn = 0x3f3f3f3f;for(int i = 0; i < g[u].size(); i++){int v = g[u][i];if(v == fa) continue;if(sm[u] - dp[v][0] + dp[v][1] + a[u] == pans){res[u] = 1;dfs2(v, u, 1);premx = max(premx, i);sufmn = min(sufmn, i);}}for(int i = 0; i < g[u].size(); i++){int v = g[u][i];if(v == fa) continue;if(i >= premx) break;dfs2(v, u, 0);}for(int i = g[u].size() - 1; i >= 0; i--){int v = g[u][i];if(v == fa) continue;if(i <= sufmn) break;dfs2(v, u, 0);}return;}int premx = -1, sufmn = 0x3f3f3f3f;for(int i = 0; i < g[u].size(); i++){int v = g[u][i];if(v == fa) continue;if(sm[u] - dp[v][0] + dp[v][1] == pans){dfs2(v, u, 1);premx = max(premx, i);sufmn = min(sufmn, i);}}for(int i = 0; i < g[u].size(); i++){int v = g[u][i];if(v == fa) continue;if(i >= premx) break;dfs2(v, u, 0);}for(int i = g[u].size() - 1; i >= 0; i--){int v = g[u][i];if(v == fa) continue;if(i <= sufmn) break;dfs2(v, u, 0);}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];for(int i = 1; i < n; i++){int u, v;cin >> u >> v;g[u].push_back(v);g[v].push_back(u);}memset(dp, 0x3f, sizeof(dp));dfs(1, 0);ans = dp[1][0];dfs2(1, 0, 0);int anscnt = 0;for(int i = 1; i <= n; i++) anscnt += res[i];cout << ans << " " << anscnt << "\n";for(int i = 1; i <= n; i++)if(res[i])cout << i << " ";return 0;
}
Sol.2 最小生成树
图论建模。把树拍成 DFS 序，把每个子树的区间 \([l, r]\) 表示在序列上区间加，通过差分发现这等价于在 \(l\) 出 \(+v\)，在 \(r+1\) 处 \(-v\)。
最后的目标是要把所有位置的值全部丢给 \(\bm{n + 1}\) 处，相当于是问使得 \(1\sim n + 1\) 连通的最小花费。直接求 MST 即可。
构造方案也是经典的，考虑 Kruskal 的过程，发现我们把比某条边权值小的边全部加入，判断这条边能否成为 MST 树边即可。这个可以在求 MST 的过程中一次实现。
时间复杂度 \(O(n\log n)\)。代码没写。