#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define in insert
#define pll pair<ll,ll>
#define vpl vector<pll>
#define vll vector <ll>
#define vl vector<ll>
#define F first
#define S second
#define ll long long
#define all(v) v.begin(),v.end()
#define endl "\n"
#define ull unsigned long long
#define ld long double
using namespace std;
using namespace __gnu_pbds;
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,fma")
const ll sz = 5e6 + 5;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll eps = 1e-12;
const ll P1 = 31; // for hashing
const ll P2 = 41; // for hashing
//template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
// ll idx = 1;
ll n, ans, dp[sz];
vll g[sz];
string s;
void dfs(ll node, ll par = -1)
{
ll sum = 0;
ll is = (s[node] == '1');
for(ll i : g[node])
{
if(i == par)
continue;
dfs(i, node);
sum += dp[i];
ans = max(ans, dp[i]);
}
dp[node] = max(is, sum - is);
ans = max(ans, dp[node]);
}
void solve()
{
cin >> n;
for(ll i = 1; i < n; i++){
ll u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
cin >> s;
s = '!' + s;
for(ll i = 1; i <= n; ++i)
dp[i] = (s[i] == '1');
dfs(1);
cout << ans + 1 << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long t = 1;
// cin >> t;
while(t--)
{
// cout << "Case #" << (int) idx <<": ";
solve();
// idx++;
}
}
/*
Note : don`t use fast input in interactive questions
Note : Compare long double with eps = 1e-12
Note : Always write 2 hashes
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
117844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
117844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
117844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
