#include <bits/stdc++.h>
using namespace std;
void fastIO() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
}
const int NMAX = 1e6;
int a[NMAX], dp[NMAX], sum[NMAX];
vector<int> G[NMAX];
void dfs(int u, int parent) {
sum[u] = a[u];
for (int v : G[u])
if (v != parent) {
dfs(v, u);
sum[u] += sum[v];
if (sum[v] > dp[u])
dp[u] = sum[v];
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
for (int i = 0; i < N - 1; ++i) {
G[S[i]].emplace_back(D[i]);
G[D[i]].emplace_back(S[i]);
}
for (int u = 0; u < N; ++u)
a[u] = pp[u];
dfs(0, -1);
int ans = 0;
for (int u = 0; u < N; ++u) {
if (dp[1] - sum[u] > dp[u])
dp[u] = dp[1] - sum[u];
if (dp[u] < dp[ans])
ans = u;
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
23756 KB |
Output is correct |
2 |
Correct |
14 ms |
23756 KB |
Output is correct |
3 |
Incorrect |
14 ms |
23832 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
23756 KB |
Output is correct |
2 |
Correct |
14 ms |
23756 KB |
Output is correct |
3 |
Incorrect |
14 ms |
23832 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
23756 KB |
Output is correct |
2 |
Correct |
14 ms |
23756 KB |
Output is correct |
3 |
Incorrect |
14 ms |
23832 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
23756 KB |
Output is correct |
2 |
Correct |
14 ms |
23756 KB |
Output is correct |
3 |
Incorrect |
14 ms |
23832 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |