#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;
const int NS = (int)2e5 + 4;
int n, k;
vector<int> way[NS];
int a[NS];
int dp[NS][4], from[NS][4][3];
void sol(int x, int pr){
int sum = 0;
for(int i = 0; i < (int)way[x].size(); ++i){
if(way[x][i] == pr){
swap(way[x][i], way[x].back());
way[x].pop_back();
break;
}
}
for(auto&nxt:way[x]){
sol(nxt, x);
sum += a[nxt];
}
for(auto&nxt:way[x]){
if(dp[nxt][2] + sum - a[nxt] > dp[x][1]){
dp[x][1] = dp[nxt][2] + sum - a[nxt];
from[x][1][0] = nxt;
}
if(dp[nxt][1] + sum - a[nxt] > dp[x][2]){
dp[x][2] = dp[nxt][1] + sum - a[nxt];
from[x][2][0] = nxt;
}
if(dp[nxt][3] > dp[x][0]){
dp[x][0] = dp[nxt][3];
from[x][0][0] = nxt, from[x][0][1] = -1;
}
}
vector<vector<int>> srt(4);
for(auto&nxt:way[x]){
srt[0].push_back(nxt);
srt[1].push_back(nxt);
srt[2].push_back(nxt);
srt[3].push_back(nxt);
}
for(int i = 0; i < 4; ++i){
sort(srt[i].begin(), srt[i].end(), [&](int&x, int&y){return dp[x][i] > dp[y][i];});
}
for(int i = 0; i < 3; ++i){
while((int)srt[i].size() > 3){
srt[i].pop_back();
}
}
for(auto&i:srt[2]){
for(auto&j:srt[0]){
if(i == j) continue;
int val = dp[i][2] + dp[j][0] + sum - a[i] - a[j];
if(val > dp[x][0]){
dp[x][0] = val;
from[x][0][0] = i, from[x][0][1] = j;
}
}
}
for(auto&i:srt[1]){
for(auto&j:srt[2]){
for(auto&k:srt[0]){
if(i == j || j == k || i == k) continue;
int val = dp[i][1] + dp[j][2] + dp[k][0] + sum - a[i] - a[j] - a[k];
if(val > dp[x][3]){
dp[x][3] = val;
from[x][3][0] = i;
from[x][3][1] = j;
from[x][3][2] = k;
}
}
}
}
for(auto&i:srt[1]){
for(auto&j:srt[3]){
if(i == j) continue;
int val = dp[i][1] + dp[j][3] + sum - a[i] - a[j];
if(val > dp[x][3]){
dp[x][3] = val;
from[x][3][0] = i;
from[x][3][1] = j;
from[x][3][2] = -1;
}
}
}
if(dp[x][0] > dp[x][3]){
dp[x][3] = dp[x][0];
from[x][3][0] = x, from[x][3][1] = -1;
}
dp[x][0] += a[x];
dp[x][1] += a[x];
dp[x][2] += a[x];
dp[x][3] += a[x];
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
memset(from, -1, sizeof(from));
cin >> n >> k;
for(int i = 1; i < n; ++i){
int x, y;
cin >> x >> y;
--x, --y;
way[x].push_back(y);
way[y].push_back(x);
}
for(int i = 0; i < n; ++i){
cin >> a[i];
}
sol(0, -1);
cout << dp[0][0] << '\n';
vector<int> ans;
auto makeout = [&](auto&&self, int A, int B)->void{
if(from[A][B][0] == -1){
ans.push_back(A);
return;
}
if(B == 1){
ans.push_back(A);
self(self, from[A][B][0], 2);
for(auto&nxt:way[A]){
if(nxt != from[A][B][0]){
ans.push_back(nxt);
}
}
}
else if(B == 2){
for(auto&nxt:way[A]){
if(nxt != from[A][B][0]){
ans.push_back(nxt);
}
}
self(self, from[A][B][0], 1);
ans.push_back(A);
}
else if(B == 0){
ans.push_back(A);
if(from[A][B][1] == -1){
self(self, from[A][B][0], 3);
}
else{
self(self, from[A][B][0], 2);
for(auto&nxt:way[A]){
if(nxt != from[A][B][0] && nxt != from[A][B][1]){
ans.push_back(nxt);
}
}
self(self, from[A][B][1], 0);
}
}
else{
if(from[A][B][1] == -1){
self(self, from[A][B][0], 0);
}
else if(from[A][B][2] == -1){
for(auto&nxt:way[A]){
if(nxt != from[A][B][0] && nxt != from[A][B][1]){
ans.push_back(nxt);
}
}
self(self, from[A][B][0], 1);
ans.push_back(A);
self(self, from[A][B][1], 3);
}
else{
for(auto&nxt:way[A]){
if(nxt != from[A][B][0] && nxt != from[A][B][1] && nxt != from[A][B][2]){
ans.push_back(nxt);
}
}
self(self, from[A][B][0], 1);
ans.push_back(A);
self(self, from[A][B][1], 2);
self(self, from[A][B][2], 0);
}
}
};
makeout(makeout, 0, 0);
cout << (int)ans.size() << '\n';
for(auto&i:ans){
cout << i + 1 << ' ';
}
cout << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
23708 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
23852 KB |
x_1 and x_2 are too far apart |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
10 ms |
23708 KB |
Output is correct |
| 3 |
Correct |
9 ms |
23764 KB |
Output is correct |
| 4 |
Correct |
12 ms |
23852 KB |
Output is correct |
| 5 |
Correct |
9 ms |
23832 KB |
Output is correct |
| 6 |
Correct |
10 ms |
23764 KB |
Output is correct |
| 7 |
Correct |
10 ms |
23764 KB |
Output is correct |
| 8 |
Correct |
12 ms |
23824 KB |
Output is correct |
| 9 |
Incorrect |
10 ms |
23764 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
10 ms |
23708 KB |
Output is correct |
| 3 |
Correct |
9 ms |
23764 KB |
Output is correct |
| 4 |
Correct |
12 ms |
23852 KB |
Output is correct |
| 5 |
Correct |
9 ms |
23832 KB |
Output is correct |
| 6 |
Correct |
10 ms |
23764 KB |
Output is correct |
| 7 |
Correct |
10 ms |
23764 KB |
Output is correct |
| 8 |
Correct |
12 ms |
23824 KB |
Output is correct |
| 9 |
Incorrect |
10 ms |
23764 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
10 ms |
23708 KB |
Output is correct |
| 3 |
Correct |
9 ms |
23764 KB |
Output is correct |
| 4 |
Correct |
12 ms |
23852 KB |
Output is correct |
| 5 |
Correct |
9 ms |
23832 KB |
Output is correct |
| 6 |
Correct |
10 ms |
23764 KB |
Output is correct |
| 7 |
Correct |
10 ms |
23764 KB |
Output is correct |
| 8 |
Correct |
12 ms |
23824 KB |
Output is correct |
| 9 |
Incorrect |
10 ms |
23764 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
24052 KB |
Output is correct |
| 2 |
Correct |
10 ms |
24004 KB |
Output is correct |
| 3 |
Incorrect |
14 ms |
24020 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
24052 KB |
Output is correct |
| 2 |
Correct |
10 ms |
24004 KB |
Output is correct |
| 3 |
Incorrect |
14 ms |
24020 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
