#include <stdio.h>
#include <stdlib.h>
#define N 200000
long long max(long long a, long long b) { return a > b ? a : b; }
int *ej[N], eo[N], ww[N];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
long long dp[N];
void dfs(int p, int i) {
int o;
dp[i] = 0;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p) {
dfs(i, j);
dp[i] = max(dp[i], dp[j]);
}
}
dp[i] += ww[i];
}
int main() {
static int qu[N];
int n, k, cnt, h, i, j, p, o;
scanf("%d%d", &n, &k);
for (i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (h = 0; h < n - 1; h++) {
scanf("%d%d", &i, &j), i--, j--;
append(i, j), append(j, i);
}
for (i = 0; i < n; i++)
scanf("%d", &ww[i]);
if (k == 1) {
dfs(-1, 0);
p = -1, i = 0, cnt = 0;
while (1) {
qu[cnt++] = i;
for (o = eo[i]; o--; ) {
j = ej[i][o];
if (j != p && dp[i] == dp[j] + ww[i]) {
i = j;
break;
}
}
if (o < 0)
break;
}
printf("%lld\n", dp[0]);
printf("%d\n", cnt);
for (h = 0; h < cnt; h++)
printf("%d ", qu[h] + 1);
printf("\n");
}
return 0;
}
Compilation message
Main.c: In function 'append':
Main.c:13:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
13 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
Main.c: In function 'main':
Main.c:39:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | scanf("%d%d", &n, &k);
| ^~~~~~~~~~~~~~~~~~~~~
Main.c:43:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | scanf("%d%d", &i, &j), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~
Main.c:47:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%d", &ww[i]);
| ^~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
95 ms |
14268 KB |
Output is correct |
4 |
Correct |
107 ms |
15104 KB |
Output is correct |
5 |
Correct |
85 ms |
15020 KB |
Output is correct |
6 |
Correct |
132 ms |
16256 KB |
Output is correct |
7 |
Correct |
73 ms |
15076 KB |
Output is correct |
8 |
Correct |
80 ms |
15308 KB |
Output is correct |
9 |
Correct |
136 ms |
33484 KB |
Output is correct |
10 |
Correct |
121 ms |
23604 KB |
Output is correct |
11 |
Correct |
64 ms |
15000 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Unexpected end of file - int64 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Unexpected end of file - int64 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Unexpected end of file - int64 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
432 KB |
Unexpected end of file - int64 expected |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
432 KB |
Unexpected end of file - int64 expected |
2 |
Halted |
0 ms |
0 KB |
- |