//#pragma GCC optimize("Ofast")
//#pragma GCC optimization("unroll-loops, no-stack-protector")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define Snape int main()
#define lumos ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define nox return 0
#define ll long long
#define pb push_back
#define Size(v) (int)v.size()
#define FOR(i, x, y) for(int i = x; i <= y; ++i)
#define trav(a, x) for(auto &a : x)
using namespace std;
using namespace __gnu_pbds;
/*
"After all this time?"
"Always"
*/
const int nax = 2e5+5;
int n, dp[nax];
vector<int> g[nax];
string s;
int ans=0;
void dfs(int v, int p=0) {
trav(c, g[v]) {
if (c==p) continue;
dfs(c, v);
}
int val = (s[v]=='1');
dp[v]=max(dp[v],val);
int sum=0;
trav(c, g[v]) {
if (c==p) continue;
sum+=dp[c];
}
dp[v]=max(dp[v],sum-val);
}
void calc(int v, int p=0) {
trav(c, g[v]) {
if (c==p) continue;
calc(c, v);
}
int val = (s[v]=='1');
if (val==0) {
int sum=0;
trav(c, g[v]) {
if (c==p) continue;
sum+=dp[c];
}
ans=max(ans,sum);
}
else {
int sum=0;
trav(c, g[v]) {
if (c == p) continue;
ans=max(ans,dp[c]+1);
sum+=dp[c];
}
ans=max(ans,sum-1);
}
}
Snape {
lumos;
cin >> n;
FOR (i,1,n-1) {
int a,b; cin>>a>>b;
g[a].pb(b);
g[b].pb(a);
}
cin >> s; s = ' ' + s;
dfs(1);
calc(1);
cout<<ans;
nox;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
4992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
