#include <bits/stdc++.h>
int main() {
// centroid decomposition
int N;
std::cin >> N;
std::vector<int> A(N - 1), B(N - 1);
std::vector<std::vector<int>> Tree(N);
for (int i = 0; i < N - 1; ++i) {
std::cin >> A[i] >> B[i];
--A[i], --B[i];
Tree[A[i]].push_back(B[i]);
Tree[B[i]].push_back(A[i]);
}
std::string S;
std::cin >> S;
std::vector<bool> isValid(N, true);
std::vector<int> subtreeSize(N), dp(N);
int answer = 0;
auto calcDp = [&](const int root) {
auto dfs = [&](auto &&self, const int v, const int p) -> int {
dp[v] = (S[v] == '1' ? 1 : 0);
int sum = 0;
for (const int t : Tree[v]) {
if (t == p or (not isValid[t])) continue;
sum += self(self, t, v);
}
if (S[v] == '1') --sum;
dp[v] = std::max(dp[v], sum);
return dp[v];
};
answer = std::max(answer, dfs(dfs, root, -1));
};
for (int i = 0; i < N; ++i) calcDp(i);
std::cout << answer << std::endl;
/*
auto centroidDecomposite = [&](auto &&self, const int root) -> void {
// calc subtree size
auto dfs1 = [&](auto &&self2, const int v, const int p) -> int {
subtreeSize[v] = 1;
for (const int t : Tree[v]) {
if (t == p or (not isValid[t])) continue;
subtreeSize[v] += self2(self2, t, v);
}
return subtreeSize[v];
};
dfs1(dfs1, root, -1);
// find centroid
const int mas = subtreeSize[root];
auto dfs2 = [&](auto &&self2, const int v, const int p) -> int {
bool isCentroid = true;
for (const int t : Tree[v]) {
if (t == p or (not isValid[t])) continue;
const int res = self2(self2, t, v);
if (res != -1) return res;
if (subtreeSize[t] > mas / 2) isCentroid = false;
}
if ((mas - subtreeSize[v]) > mas/ 2) isCentroid = false;
return isCentroid ? v : -1;
};
const int centroid = dfs2(dfs2, root, -1);
// dp
calcDp(centroid);
// rec
isValid[centroid] = false;
for (const int t : Tree[centroid]) {
if (isValid[t]) {
self(self, t);
}
}
};
centroidDecomposite(centroidDecomposite, 0);
std::cout << answer << std::endl;*/
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |