《CF1120D Power Tree》
题目描述
给定一棵有 n 个顶点的有根树，树的根为顶点 1。每个顶点都有一个非负的价格。树的叶子是指度为 1 且不是根的顶点。
Arkady 和 Vasily 在树上玩一个奇怪的游戏。游戏分为三个阶段。第一阶段，Arkady 购买树上的一些非空顶点集合。第二阶段，Vasily 给所有叶子节点赋一些整数。第三阶段，Arkady 可以进行若干次（也可以不进行）如下操作：选择他在第一阶段购买的某个顶点 v 和某个整数 x，然后将 x 加到 v 的子树中所有叶子的整数上。整数 x 可以是正数、负数或零。
如果一条从叶子 a 到根的简单路径经过顶点 b，则称叶子 a 在顶点 b 的子树中。
Arkady 的目标是让所有叶子上的整数都变为零。无论 Vasily 在第二阶段如何赋值，Arkady 都要保证自己能够达成目标。请你求出 Arkady 在第一阶段至少需要支付的总费用 s，以及有多少个顶点属于至少一个最优集合（即总费用为 s 的集合），使得 Arkady 购买这些顶点后能够保证胜利。
请你输出所有属于至少一个最优集合的顶点编号。
输入格式
第一行包含一个整数 n（2≤n≤200000），表示树的顶点数。
第二行包含 n 个整数 c1,c2,…,cn（0≤ci≤109），其中 ci 表示第 i 个顶点的价格。
接下来的 n−1 行，每行包含两个整数 a 和 b（1≤a,b≤n），表示树上的一条边。
输出格式
第一行输出两个整数：Arkady 至少需要支付的最小总费用 s，以及属于至少一个最优集合的顶点个数 k。
第二行输出 k 个不同的整数，按升序排列，表示属于至少一个最优集合的顶点编号。
显示翻译
题意翻译
输入输出样例
输入 #1复制
5 5 1 3 2 1 1 2 2 3 2 4 1 5
输出 #1复制
4 3 2 4 5
输入 #2复制
3 1 1 1 1 2 1 3
输出 #2复制
2 3 1 2 3
说明/提示
在第二个样例中，所有包含两个顶点的集合都是最优的。因此，每个顶点都至少属于一个最优集合。
由 ChatGPT 4.1 翻译
代码实现：
#include <bits/stdc++.h>
using namespace std;
#define LONG_LONG long long
const int MAX_NODE = 2e5 + 5;
int node_count; // 节点总数
int degree[MAX_NODE]; // 每个节点的度数
int weight[MAX_NODE]; // 每个节点的权重
LONG_LONG dp[MAX_NODE][2]; // 动态规划数组，dp[u][0/1]表示节点u的两种状态
vector<int> graph[MAX_NODE]; // 图的邻接表表示
vector<int> parent_choices[MAX_NODE][2]; // 记录每个状态下的父节点选择
// 深度优先搜索，计算dp值
void dfs(int current_node, int parent_node) {
// 如果是叶子节点（度数为1且有父节点）
if (degree[current_node] == 1 && parent_node != 0) {
dp[current_node][1] = weight[current_node]; // 选择当前节点
dp[current_node][0] = 0; // 不选择当前节点
return;
}
LONG_LONG sum = 0;
// 计算所有子节点选择状态下的和
for (int i = 0; i < graph[current_node].size(); ++i) {
int child_node = graph[current_node][i];
if (child_node != parent_node) {
dfs(child_node, current_node);
sum += dp[child_node][1];
}
}
// 初始化当前节点的两种状态
dp[current_node][1] = sum;
dp[current_node][0] = sum;
// 尝试更新当前节点的两种状态
for (int i = 0; i < graph[current_node].size(); ++i) {
int child_node = graph[current_node][i];
if (child_node != parent_node) {
// 更新选择当前节点的状态
dp[current_node][1] = min(dp[current_node][1], sum - dp[child_node][1] + dp[child_node][0] + weight[current_node]);
// 更新不选择当前节点的状态
dp[current_node][0] = min(dp[current_node][0], sum - dp[child_node][1] + dp[child_node][0]);
}
}
// 记录每个状态下的父节点选择
for (int i = 0; i < graph[current_node].size(); ++i) {
int child_node = graph[current_node][i];
if (child_node != parent_node) {
if (dp[current_node][1] == sum - dp[child_node][1] + dp[child_node][0] + weight[current_node]) {
parent_choices[current_node][1].push_back(child_node);
}
if (dp[current_node][0] == sum - dp[child_node][1] + dp[child_node][0]) {
parent_choices[current_node][0].push_back(child_node);
}
}
}
}
bool selected[MAX_NODE]; // 标记节点是否被选中
bool visited[MAX_NODE][2]; // 标记节点的状态是否已访问
// 节点结构体，用于BFS
struct Node {
int node; // 当前节点
int parent; // 父节点
int state; // 状态（0或1）
};
queue<Node> q; // BFS队列
// 广度优先搜索，确定最终选择的节点
void bfs() {
q.push({1, 0, 1}); // 从根节点（1号节点）开始，状态为1
while (!q.empty()) {
Node current = q.front();
q.pop();
int current_node = current.node;
int parent_node = current.parent;
int current_state = current.state;
// 如果是叶子节点
if (degree[current_node] == 1 && parent_node != 0) {
if (current_state) {
selected[current_node] = true;
}
continue;
}
// 重新计算子节点选择状态的和
LONG_LONG sum = 0;
for (int i = 0; i < graph[current_node].size(); ++i) {
int child_node = graph[current_node][i];
if (child_node != parent_node) {
sum += dp[child_node][1];
}
}
// 处理特殊情况
if (sum == dp[current_node][current_state]) {
for (int i = 0; i < graph[current_node].size(); ++i) {
int child_node = graph[current_node][i];
if (child_node != parent_node && !visited[child_node][1]) {
visited[child_node][1] = true;
q.push({child_node, current_node, 1});
}
}
}
// 根据父节点选择数量处理不同情况
if (parent_choices[current_node][current_state].size() == 1) {
// 只有一个选择的情况
if (current_state || weight[current_node] == 0) {
selected[current_node] = true;
}
int chosen_child = parent_choices[current_node][current_state][0];
for (int i = 0; i < graph[current_node].size(); ++i) {
int child_node = graph[current_node][i];
if (child_node != parent_node && child_node != chosen_child && !visited[child_node][1]) {
visited[child_node][1] = true;
q.push({child_node, current_node, 1});
}
}
if (!visited[chosen_child][0]) {
visited[chosen_child][0] = true;
q.push({chosen_child, current_node, 0});
}
} else if (parent_choices[current_node][current_state].size() > 1) {
// 多个选择的情况
if (current_state || weight[current_node] == 0) {
selected[current_node] = true;
}
for (int i = 0; i < graph[current_node].size(); ++i) {
int child_node = graph[current_node][i];
if (child_node != parent_node && !visited[child_node][1]) {
q.push({child_node, current_node, 1});
}
}
for (int i = 0; i < parent_choices[current_node][current_state].size(); ++i) {
int child_node = parent_choices[current_node][current_state][i];
if (!visited[child_node][0]) {
visited[child_node][0] = true;
q.push({child_node, current_node, 0});
}
}
}
}
}
int main() {
scanf("%d", &node_count);
// 读取节点权重
for (int i = 1; i <= node_count; ++i) {
scanf("%d", &weight[i]);
}
// 读取边信息，构建图
for (int i = 1; i < node_count; ++i) {
int x, y;
scanf("%d%d", &x, &y);
graph[x].push_back(y);
graph[y].push_back(x);
degree[x]++;
degree[y]++;
}
// 计算dp值
dfs(1, 0);
// 确定选择的节点
bfs();
// 统计并输出结果
int selected_count = 0;
for (int i = 1; i <= node_count; ++i) {
if (selected[i]) {
selected_count++;
}
}
printf("%lld %d\n", dp[1][1], selected_count);
for (int i = 1; i <= node_count; ++i) {
if (selected[i]) {
printf("%d ", i);
}
}
return 0;
}