題目描述
給定一棵有?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;
}
?
