CF1120D-Power Tree
题目:
题目描述:
You are given a rooted tree with $ n $ vertices, the root of the tree is the vertex $ 1 $ . Each vertex has some non-negative price. A leaf of the tree is a non-root vertex that has degree $ 1 $ .
Arkady and Vasily play a strange game on the tree. The game consists of three stages. On the first stage Arkady buys some non-empty set of vertices of the tree. On the second stage Vasily puts some integers into all leaves of the tree. On the third stage Arkady can perform several (possibly none) operations of the following kind: choose some vertex $ v $ he bought on the first stage and some integer $ x $ , and then add $ x $ to all integers in the leaves in the subtree of $ v $ . The integer $ x $ can be positive, negative of zero.
A leaf $ a $ is in the subtree of a vertex $ b $ if and only if the simple path between $ a $ and the root goes through $ b $ .
Arkady’s task is to make all integers in the leaves equal to zero. What is the minimum total cost $ s $ he has to pay on the first stage to guarantee his own win independently of the integers Vasily puts on the second stage? Also, we ask you to find all such vertices that there is an optimal (i.e. with cost $ s $ ) set of vertices containing this one such that Arkady can guarantee his own win buying this set on the first stage.
输入格式:
The first line contains a single integer $ n $ ( $ 2 \le n \le 200,000 $ ) — the number of vertices in the tree.
The second line contains $ n $ integers $ c_1, c_2, \ldots, c_n $ ( $ 0 \le c_i \le 10^9 $ ), where $ c_i $ is the price of the $ i $ -th vertex.
Each of the next $ n - 1 $ lines contains two integers $ a $ and $ b $ ( $ 1 \le a, b \le n $ ), denoting an edge of the tree.
输出格式:
In the first line print two integers: the minimum possible cost $ s $ Arkady has to pay to guarantee his own win, and the number of vertices $ k $ that belong to at least one optimal set.
In the second line print $ k $ distinct integers in increasing order the indices of the vertices that belong to at least one optimal set.
样例:
样例输入1:
1
2
3
4
5
6
| 5
5 1 3 2 1
1 2
2 3
2 4
1 5
|
样例输出1:
样例输入2:
样例输出2:
思路:
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
| #include <bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 2e5 + 5;
int n, deg[maxn], w[maxn];
LL d[maxn][2];
vector<int> G[maxn];
vector<int> p[maxn][2];
void dfs(int u, int fa)
{
if (deg[u] == 1 && fa)
{
d[u][1] = w[u], d[u][0] = 0;
return;
}
LL tmp = 0;
for (int i = 0, v; i < G[u].size(); ++i)
if ((v = G[u][i]) != fa)
{
dfs(v, u);
tmp += d[v][1];
}
d[u][1] = d[u][0] = tmp;
for (int i = 0, v; i < G[u].size(); ++i)
if ((v = G[u][i]) != fa)
{
d[u][1] = min(d[u][1], tmp - d[v][1] + d[v][0] + w[u]), d[u][0] = min(d[u][0], tmp - d[v][1] + d[v][0]);
}
for (int i = 0, v; i < G[u].size(); ++i)
if ((v = G[u][i]) != fa)
{
if (d[u][1] == tmp - d[v][1] + d[v][0] + w[u])
p[u][1].push_back(v);
if (d[u][0] == tmp - d[v][1] + d[v][0])
p[u][0].push_back(v);
//转移可能多于一种，用vector存
}
}
bool chose[maxn], vis[maxn][2];
struct Node
{
int u, fa, tp;
};
queue<Node> Q;
void bfs()
{
Q.push((Node){1, 0, 1});
while (!Q.empty())
{
int u = Q.front().u, fa = Q.front().fa, tp = Q.front().tp;
Q.pop();
if (deg[u] == 1 && fa)
{
if (tp)
chose[u] = 1;
continue;
}
//在这里重新做一遍……主要是要特判一些特殊的情况
LL tmp = 0;
for (int i = 0, v; i < G[u].size(); ++i)
if ((v = G[u][i]) != fa)
{
tmp += d[v][1];
}
if (tmp == d[u][tp]) //在这种情况下p不一定为空，而如果不进行这个特判可能会使后面原本可以作为d(v,1)的v被跳过
{
for (int i = 0, v; i < G[u].size(); ++i)
if ((v = G[u][i]) != fa && !vis[v][1])
vis[v][1] = 1, Q.push((Node){v, u, 1});
}
if (p[u][tp].size() == 1) //它和之前的并不互斥
{
if (tp || w[u] == 0)
chose[u] = 1;
for (int i = 0, v; i < G[u].size(); ++i)
if ((v = G[u][i]) != fa && v != p[u][tp][0] && !vis[v][1])
{
vis[v][1] = 1;
Q.push((Node){v, u, 1});
}
if (!vis[p[u][tp][0]][0])
vis[p[u][tp][0]][0] = 1, Q.push((Node){p[u][tp][0], u, 0});
}
else if (p[u][tp].size() > 1)
{ //在这种情况下，所有子节点都有可能作为d(v,1)加入
if (tp || w[u] == 0)
chose[u] = 1;
for (int i = 0, v; i < G[u].size(); ++i)
if ((v = G[u][i]) != fa && !vis[v][1])
Q.push((Node){v, u, 1});
for (int i = 0; i < p[u][tp].size(); ++i)
{
if (!vis[p[u][tp][i]][0])
vis[p[u][tp][i]][0] = 1, Q.push((Node){p[u][tp][i], u, 0});
}
}
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d", &w[i]);
for (int i = 1; i < n; ++i)
{
int x, y;
scanf("%d%d", &x, &y);
G[x].push_back(y), G[y].push_back(x);
++deg[x], ++deg[y];
}
dfs(1, 0);
bfs();
int tot = 0;
for (int i = 1; i <= n; ++i)
if (chose[i])
++tot;
printf("%lld %d\n", d[1][1], tot);
for (int i = 1; i <= n; ++i)
if (chose[i])
printf("%d ", i);
return 0;
}
|