#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
ll arr[200002];
vector<int> link[200002];
void solvek1();
void solvek2();
void solvek3();
int main(){
scanf("%d %d", &n, &k);
for(int i=1; i<n; i++){
int x, y;
scanf("%d %d", &x, &y);
link[x].push_back(y);
link[y].push_back(x);
}
for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
if(k==1) solvek1();
if(k==2) solvek2();
if(k==3) solvek3();
}
namespace solve1{
int par[200002];
ll depth[200002];
void dfs(int x, int p=-1){
depth[x] += arr[x];
for(auto y: link[x]){
if(y==p) continue;
depth[y] = depth[x], par[y] = x;
dfs(y, x);
}
}
void solve(){
dfs(1);
int x = max_element(depth+1, depth+n+1) - depth;
vector<int> v;
while(x) v.push_back(x), x = par[x];
reverse(v.begin(), v.end());
printf("%lld\n%d\n", depth[v.back()], (int)v.size());
for(auto x: v) printf("%d ", x);
}
}
void solvek1(){
solve1::solve();
}
namespace solve2{
int par[200002];
ll depth[200002];
vector<int> child[200002];
void dfsChild(int x, int p=-1){
for(auto y: link[x]){
if(y==p) continue;
child[x].push_back(y), par[y] = x, depth[y] = depth[x] + 1;
dfsChild(y, x);
}
}
ll U[200002][2]; /// ���ƿ��� DP, [0]�� x �θ� ����, [1]�� x���� ����
int trackU[200002][2]; /// ������ �뵵
void dfsU(int x){
if(child[x].empty()){ /// ���� ����� ���
U[x][0] = U[x][1] = arr[x];
return;
}
vector<pair<ll, int> > profit_pointToU0, profit_pointToU1;
ll pointSum = arr[x]; /// �ڱ� ���� �ڽĵ��� ��� ������ ���� ��
for(int y: child[x]){
dfsU(y);
pointSum += arr[y];
profit_pointToU0.push_back(make_pair(U[y][0] - arr[y], y));
profit_pointToU1.push_back(make_pair(U[y][1] - arr[y], y));
}
sort(profit_pointToU0.rbegin(), profit_pointToU0.rend());
sort(profit_pointToU1.rbegin(), profit_pointToU1.rend());
/// U[x][0]: �θ� ����� x�� ��� �ִ� ä�� �Ʒ��� ��ȸ�ϰ� ���ƿ��� ���
/// point �� �� �ϳ��� U[y][1]�� �ٲ� �� �ִ�.
assert(profit_pointToU0[0].first >= 0);
U[x][0] = pointSum + profit_pointToU1[0].first;
trackU[x][0] = profit_pointToU1[0].second;
/// U[x][1]: x���� ����� �θ� ��� �ִ� ä�� �Ʒ��� ��ȸ�ϰ� ���ƿ��� ���
/// point �� �� �ϳ��� U[y][0]���� �ٲ� �� �ִ�.
assert(profit_pointToU1[0].first >= 0);
U[x][1] = pointSum + profit_pointToU0[0].first;
trackU[x][1] = profit_pointToU0[0].second;
}
ll I[200002][2]; /// ���ƿ��� �ʴ� DP, [0]�� x �θ� ����, [1]�� x���� ����
int typeI[200002][2], trackI[200002][2], trackI2[200002][2]; /// ������ �뵵
/// type -1: I[0]->I[1]�� �ٲ� ��, 0: �ܿ� ��� ì��� ������ ��, 1: �׳� �ϳ��� ������ ��
void dfsI(int x){
if(child[x].empty()){
I[x][0] = I[x][1] = arr[x];
return;
}
vector<pair<ll, int> > profit_pointToU0, profit_pointToU1;
vector<pair<ll, int> > profit_pointToI0, profit_pointToI1;
ll pointSum = arr[x];
for(auto y: child[x]){
dfsI(y);
pointSum += arr[y];
profit_pointToU0.push_back(make_pair(U[y][0] - arr[y], y));
profit_pointToU1.push_back(make_pair(U[y][1] - arr[y], y));
profit_pointToI0.push_back(make_pair(I[y][0] - arr[y], y));
profit_pointToI1.push_back(make_pair(I[y][1] - arr[y], y));
}
sort(profit_pointToU0.rbegin(), profit_pointToU0.rend());
sort(profit_pointToU1.rbegin(), profit_pointToU1.rend());
sort(profit_pointToI0.rbegin(), profit_pointToI0.rend());
sort(profit_pointToI1.rbegin(), profit_pointToI1.rend());
/// I[x][1]: x���� ����� �Ʒ��� �������� �ִ�
/// Case 1. �ڽ� �� �ϳ��� I[0]�� ���� �� �ִ�.
for(auto y: child[x]) if(I[x][1] < arr[x] + I[y][0]){
I[x][1] = arr[x] + I[y][0];
typeI[x][1] = 1, trackI[x][1] = y;
}
/// Case 2. �ڽ� �� �ϳ��� U[0] or U[1]�� ���ϰ�, �ܿ� ��带 ��, ���� �ڽ� �� �ϳ��� I[1]�� ���� �� �ִ�.
for(auto a: child[x]) for(auto b: child[x]){
if(a==b) continue;
ll v = pointSum - arr[a] - arr[b] + max(U[a][0], U[a][1]) + I[b][1];
if(I[x][1] >= v) continue;
I[x][1] = v, typeI[x][1] = 0, trackI[x][1] = a, trackI2[x][1] = b;
}
/// I[x][0]: x �θ� ����� �Ʒ��� �������� �ִ�
/// Case 0. I[1]�� ���Ѵ�.
I[x][0] = I[x][1], typeI[x][0] = -1;
/// Case 1. �ڽ� �� �ϳ��� I[0]�� ���� �� �ִ�.
for(auto y: child[x]) if(I[x][0] < arr[x] + I[y][0]){
I[x][0] = arr[x] + I[y][0];
typeI[x][0] = 1, trackI[x][1] = y;
}
/// Case 2. �ڽ� �� �ϳ��� U[1]�� ���ϰ�, �ܿ� ��带 ��, ���� �ڽ� �� �ϳ��� I[1]�� ���� �� �ִ�.
for(auto a: child[x]) for(auto b: child[x]){
if(a==b) continue;
ll v = pointSum - arr[a] - arr[b] + U[a][1] + I[b][1];
if(I[x][0] >= v) continue;
I[x][0] = v, typeI[x][0] = 0, trackI[x][0] = a, trackI2[x][0] = b;
}
}
vector<int> ans;
void track(int x, char type, int j){
if(type == 'U'){
if(trackU[x][j] == 0) ans.push_back(x);
else if(j==0){
int nxt = trackU[x][j];
for(auto y: child[x]) if(y != nxt) ans.push_back(y);
track(nxt, 'U', 1);
ans.push_back(x);
}
else if(j==1){
int nxt = trackU[x][j];
ans.push_back(x);
track(nxt, 'U', 0);
for(auto y: child[x]) if(y != nxt) ans.push_back(y);
}
}
else if(type == 'I'){
if(trackI[x][j] == 0) ans.push_back(x);
else if(typeI[x][j] == -1) track(x, 'I', !j);
else if(j==0){
if(typeI[x][j] == 0){
int a = trackI[x][j], b = trackI2[x][j];
track(a, 'U', 1);
ans.push_back(x);
for(auto y: child[x]) if(y!=a && y!=b) ans.push_back(y);
track(b, 'I', 1);
}
else{
int a = trackI[x][j];
ans.push_back(x);
track(a, 'I', 0);
}
}
else{
if(typeI[x][j] == 0){
int a = trackI[x][j], b = trackI2[x][j];
ans.push_back(x);
track(a, 'U', 0);
for(auto y: child[x]) if(y!=a && y!=b) ans.push_back(y);
track(b, 'I', 1);
}
else{
int a = trackI[x][j];
ans.push_back(x);
track(a, 'I', 0);
}
}
}
}
void solve(){
dfsChild(1);
dfsU(1);
dfsI(1);
// printf("Dfs Results\n");
// for(int i=1; i<=n; i++){
// printf("%2d: U0 %2lld U1 %2lld I0 %2lld I1 %2lld\n", i, U[i][0], U[i][1], I[i][0], I[i][1]);
// }
if(I[1][1] >= U[1][1]){
printf("%lld\n", I[1][1]);
track(1, 'I', 1);
}
else{
printf("%lld\n", U[1][1]);
track(1, 'U', 1);
}
printf("%d\n", (int)ans.size());
for(auto x: ans) printf("%d ", x);
}
}
void solvek2(){
solve2::solve();
}
namespace solve3{
int par[200002];
ll depth[200002];
vector<int> child[200002];
void dfs(int x, int p=-1){
for(auto y: link[x]){
if(y==p) continue;
par[y] = x, depth[y] = depth[x] + 1;
child[x].push_back(y);
dfs(y, x);
}
}
vector<int> ans;
bool chk[200002];
void solve(){
dfs(1);
int coolTime = 1;
vector<int> vec (1, 1);
while(!vec.empty()){
int x = vec.back(); coolTime--;
if(coolTime == 0){
assert(!chk[x]);
chk[x] = 1, ans.push_back(x), coolTime = 3;
}
if(child[x].empty()){
if(!chk[x]) chk[x] = 1, ans.push_back(x), coolTime = 3;
vec.pop_back();
}
else{
int y = child[x].back(); child[x].pop_back();
vec.push_back(y);
}
}
printf("%lld\n%d\n", accumulate(arr+1, arr+n+1, 0LL), n);
for(int x: ans) printf("%d ", x);
}
}
void solvek3(){
solve3::solve();
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | scanf("%d %d", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:23:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14420 KB |
Output is correct |
2 |
Correct |
7 ms |
14420 KB |
Output is correct |
3 |
Correct |
109 ms |
24748 KB |
Output is correct |
4 |
Correct |
101 ms |
24780 KB |
Output is correct |
5 |
Correct |
97 ms |
24556 KB |
Output is correct |
6 |
Correct |
115 ms |
25348 KB |
Output is correct |
7 |
Correct |
78 ms |
25344 KB |
Output is correct |
8 |
Correct |
93 ms |
24900 KB |
Output is correct |
9 |
Correct |
148 ms |
39240 KB |
Output is correct |
10 |
Correct |
152 ms |
32000 KB |
Output is correct |
11 |
Correct |
73 ms |
24500 KB |
Output is correct |
12 |
Correct |
7 ms |
14420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14420 KB |
Output is correct |
2 |
Incorrect |
7 ms |
14372 KB |
total profit is not correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14420 KB |
Output is correct |
2 |
Incorrect |
7 ms |
14372 KB |
total profit is not correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14420 KB |
Output is correct |
2 |
Incorrect |
7 ms |
14372 KB |
total profit is not correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14548 KB |
Output is correct |
2 |
Correct |
8 ms |
14536 KB |
Output is correct |
3 |
Correct |
7 ms |
14548 KB |
Output is correct |
4 |
Correct |
8 ms |
14548 KB |
Output is correct |
5 |
Correct |
8 ms |
14548 KB |
Output is correct |
6 |
Correct |
10 ms |
14548 KB |
Output is correct |
7 |
Correct |
7 ms |
14420 KB |
Output is correct |
8 |
Correct |
9 ms |
14428 KB |
Output is correct |
9 |
Correct |
8 ms |
14580 KB |
Output is correct |
10 |
Correct |
8 ms |
14572 KB |
Output is correct |
11 |
Correct |
8 ms |
14548 KB |
Output is correct |
12 |
Correct |
8 ms |
14548 KB |
Output is correct |
13 |
Correct |
7 ms |
14548 KB |
Output is correct |
14 |
Correct |
7 ms |
14548 KB |
Output is correct |
15 |
Correct |
8 ms |
14544 KB |
Output is correct |
16 |
Correct |
8 ms |
14548 KB |
Output is correct |
17 |
Correct |
8 ms |
14548 KB |
Output is correct |
18 |
Correct |
8 ms |
14548 KB |
Output is correct |
19 |
Correct |
8 ms |
14548 KB |
Output is correct |
20 |
Correct |
8 ms |
14508 KB |
Output is correct |
21 |
Correct |
8 ms |
14572 KB |
Output is correct |
22 |
Correct |
8 ms |
14768 KB |
Output is correct |
23 |
Correct |
8 ms |
14548 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
14548 KB |
Output is correct |
2 |
Correct |
8 ms |
14536 KB |
Output is correct |
3 |
Correct |
7 ms |
14548 KB |
Output is correct |
4 |
Correct |
8 ms |
14548 KB |
Output is correct |
5 |
Correct |
8 ms |
14548 KB |
Output is correct |
6 |
Correct |
10 ms |
14548 KB |
Output is correct |
7 |
Correct |
7 ms |
14420 KB |
Output is correct |
8 |
Correct |
9 ms |
14428 KB |
Output is correct |
9 |
Correct |
8 ms |
14580 KB |
Output is correct |
10 |
Correct |
8 ms |
14572 KB |
Output is correct |
11 |
Correct |
8 ms |
14548 KB |
Output is correct |
12 |
Correct |
8 ms |
14548 KB |
Output is correct |
13 |
Correct |
7 ms |
14548 KB |
Output is correct |
14 |
Correct |
7 ms |
14548 KB |
Output is correct |
15 |
Correct |
8 ms |
14544 KB |
Output is correct |
16 |
Correct |
8 ms |
14548 KB |
Output is correct |
17 |
Correct |
8 ms |
14548 KB |
Output is correct |
18 |
Correct |
8 ms |
14548 KB |
Output is correct |
19 |
Correct |
8 ms |
14548 KB |
Output is correct |
20 |
Correct |
8 ms |
14508 KB |
Output is correct |
21 |
Correct |
8 ms |
14572 KB |
Output is correct |
22 |
Correct |
8 ms |
14768 KB |
Output is correct |
23 |
Correct |
8 ms |
14548 KB |
Output is correct |
24 |
Correct |
151 ms |
30376 KB |
Output is correct |
25 |
Correct |
156 ms |
30336 KB |
Output is correct |
26 |
Correct |
148 ms |
30416 KB |
Output is correct |
27 |
Correct |
176 ms |
30368 KB |
Output is correct |
28 |
Correct |
228 ms |
30412 KB |
Output is correct |
29 |
Correct |
152 ms |
30912 KB |
Output is correct |
30 |
Correct |
133 ms |
29376 KB |
Output is correct |
31 |
Correct |
146 ms |
30864 KB |
Output is correct |
32 |
Correct |
124 ms |
29316 KB |
Output is correct |
33 |
Correct |
200 ms |
31012 KB |
Output is correct |
34 |
Correct |
123 ms |
29264 KB |
Output is correct |
35 |
Correct |
95 ms |
28552 KB |
Output is correct |
36 |
Correct |
125 ms |
30784 KB |
Output is correct |
37 |
Correct |
122 ms |
28988 KB |
Output is correct |
38 |
Correct |
110 ms |
28752 KB |
Output is correct |
39 |
Correct |
170 ms |
49592 KB |
Output is correct |
40 |
Correct |
167 ms |
38236 KB |
Output is correct |
41 |
Correct |
147 ms |
33392 KB |
Output is correct |
42 |
Correct |
149 ms |
34152 KB |
Output is correct |
43 |
Correct |
198 ms |
32132 KB |
Output is correct |
44 |
Correct |
149 ms |
31108 KB |
Output is correct |
45 |
Correct |
95 ms |
29984 KB |
Output is correct |
46 |
Correct |
94 ms |
28992 KB |
Output is correct |