#include <bits/stdc++.h>
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;
const int mn = 2e5 + 5, bm = (1 << 11) + 1, mod = 1e9 + 7, offset = 5e4, B = 320 + 5;
const int inf = 1e9, base = 311;
vector <int> a[mn];
int n, dp[mn], on[mn], ans = 0;
void dfs(int u, int p){
for(auto v : a[u]){
if(v == p) continue;
dfs(v, u);
}
int max_val = 0, sum = 0;
for(auto v : a[u]){
if(v == p) continue;
sum += dp[v], max_val = max(max_val, dp[v]);
}
if(on[u]){
ans = max(ans, max_val + 1);
if(sum <= 1){
dp[u] = 1;
ans = max(ans, dp[u]);
}
else{
dp[u] = sum - 1;
ans = max(ans, dp[u]);
}
}
else{
dp[u] = sum;
ans = max(ans, dp[u]);
}
}
void solve(){
cin >> n;
for(int i = 1; i < n; i++){
int u, v; cin >> u >> v;
a[u].push_back(v);
a[v].push_back(u);
}
string s; cin >> s;
s = "#" + s;
for(int i = 1; i <= n; i++) on[i] = s[i] - '0';
dfs(1, 0);
cout << ans << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t = 1;
// cin >> t;
while(t --){
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |