#include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define all_of(v) (v).begin(), (v).end()
#define sort_unique(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define fi first
#define se second
const int MAXN = 200005;
const LL INF = (LL) 1e9 + 8763;
//const LL MOD = (LL) 1e9 + 7;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, dp[MAXN][2], have[MAXN], ans = -INF;
vector<int> G[MAXN];
void dfs(int v, int p) {
dp[v][0] = dp[v][1] = 0;
int maxv = 0, sum = 0, ch = 0;
for (int to : G[v]) {
if (to == p) continue;
dfs(to, v);
maxv = max({maxv, dp[to][0], dp[to][1] - 2 * have[to], have[to]});
sum += max({0, dp[to][0], dp[to][1] - 2 * have[to], have[to]});
ch++;
}
if (ch == 0) {
dp[v][0] = -have[v];
dp[v][1] = have[v];
// cout << "At " << v << " -> " << dp[v][0] << ' ' << dp[v][1] << '\n';
return;
}
dp[v][0] = sum - have[v];
dp[v][1] = maxv + have[v];
ans = max(ans, dp[v][0]);
ans = max(ans, dp[v][1]);
// cout << "At " << v << " -> " << dp[v][0] << ' ' << dp[v][1] << '\n';
}
void solve() {
cin >> n;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
string s;
cin >> s;
for (int i = 0; i < n; i++) {
have[i + 1] = s[i] == '1';
}
dfs(1, 1);
cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int tc = 1;
// cin >> tc;
for (int i = 1; i <= tc; i++) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
