#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 202300
#define MAXS 500
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int C[MAX];
vector<int> adj[MAX];
int N, K;
namespace k1 {
ll sum[MAX];
int mv[MAX];
void dfs(int x, int p = 0) {
sum[x] = C[x];
for (auto v : adj[x]) if (v != p) {
dfs(v, x);
if (sum[v] > sum[mv[x]]) mv[x] = v;
}
sum[x] += sum[mv[x]];
}
void solve() {
dfs(1);
vector<int> ansv;
int v = 1;
ll ans = 0;
while (1) {
ansv.push_back(v);
ans += C[v];
v = mv[v];
if (!v) break;
}
cout << ans << ln;
cout << ansv.size() << ln;
for (auto v : ansv) cout << v << bb;
}
}
namespace k2 {
void solve() {
}
}
namespace k3 {
void solve() {
}
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N >> K;
int i, a, b;
for (i = 1; i < N; i++) {
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for (i = 1; i <= N; i++) cin >> C[i];
if (K == 1) k1::solve();
if (K == 2) assert(0);
if (K == 3) k3::solve();
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
5076 KB |
Output is correct |
2 |
Correct |
3 ms |
5076 KB |
Output is correct |
3 |
Correct |
99 ms |
14688 KB |
Output is correct |
4 |
Correct |
127 ms |
14628 KB |
Output is correct |
5 |
Correct |
89 ms |
14484 KB |
Output is correct |
6 |
Correct |
93 ms |
15132 KB |
Output is correct |
7 |
Correct |
56 ms |
14376 KB |
Output is correct |
8 |
Correct |
106 ms |
14828 KB |
Output is correct |
9 |
Correct |
144 ms |
35396 KB |
Output is correct |
10 |
Correct |
126 ms |
25016 KB |
Output is correct |
11 |
Correct |
62 ms |
14028 KB |
Output is correct |
12 |
Correct |
2 ms |
5076 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
6 ms |
10068 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
6 ms |
10068 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
6 ms |
10068 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
5076 KB |
Unexpected end of file - int64 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
5076 KB |
Unexpected end of file - int64 expected |
2 |
Halted |
0 ms |
0 KB |
- |