/*====================*\
| |
| written by Franuch |
| |
\*====================*/
/* \/ *\
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&&&&&&&&&#&#&&&&&&&&&&&&#####B#####BBBBBB######&&&&&&&&@&&&@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&&&&&&##&&&&&&&&&&&&&&&&######BBBBBBBB#########&&&&&&&&&@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&@&&@@@@@@@@&##&#########BBBGGGGGGGBBBBB##############&&@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&@@@@@@@@@@@@@@@@@@@&#BBBBBBBBGGGGGGGGGGGBBBBBBBBBBBB#####&&@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#BGPGGGGGGGGGGGGGGGGGBGBBBBBBB######&&&
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&&&@@@@@@@@@@@@@#BPPPPPPPPPGGGGGGGGGBBBBBBBBBB#####&&
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&BG5YJ?777?J5G#&@@@@@&&@#GPPPPPPPPPGGGGGGGBBBBBBBBBB#####&&
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&G5J!~^^^^::::::^^~7JPB&@@@@@@@#GPPP5PPPGGGGGGGGGGBBBBBBBBB##&&
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@G?~^^::::::::::.....:^^~7?5G#@@@@@&G55P55PPGGGGGGGGGBBBBBBBBB####
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@G!.::::::::^^::.... ...:^~!7?JYP#@@@&G55PPPPPGGGGGGGGGBBBBBBBBB###
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@?..:::::::::::..... ...:^^!7JYYPB&@@@B55PPPPGGGGGGGGGGBBBBBBBB###
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&! .::^^^^:::::............::^~!?YPGB#&@@@@#PPPPPGGGBBBBBBBBBBBBBBB###
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@J.:::^~!!!~~^^^::::...::..::~7?Y5PG#&@@@@@@@#GPGGGGBBBBBBBBBBBBBBBB###
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@B~^^^^~!7!!!~^^:......:!^::^^^~!7?J5G#&&@@@@@@#GGGGBBBBBBBBBBBBBBBBB###
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@5~~~~!7!!!!7777!7?7~~.:7:.:^^:^7YPG#&@@@@@@@@@@BGGGGBB####BBBBBBBBB####
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@5?7?JJ??Y5GGB#&&@@&##Y??. .~?!J#@@@@@@@@@@@@@@@@BGGGBB#######BBBBBB####
@@@@@@@@@@@@@@@@@@@@@@@@@@@@&5555Y5G&@@@@@@@@@@@@@@#?. ^YG&@@@@@@@@@@@@@@@@@&GPGGBB######BBBBBB####
@@@@@@@@@@@@@@@@@@@@@@@@@@@@BPGGB#@@@@@@@@@@&&@&@&&B?:..^Y@@@@@@@@@@@@@@@@@@@@BPPGBBBBB####BBBBB####
@@@@@@@@@@@@@@@@@@@@@@@@@@@&GGB&@@@@@@@&##&@&#B#&@#BY~^^7G@@@@@@@@@@@@@@@@@@@@#PPGGBBB#B###BBBBB####
@@@@@@@@@@@@@@@@@@@@@@@@@@@BPG#&@@@@&#BGGB#&@@B5P#&B57^!5&@@@@@@@@@@@@@@@@@@@@&PPGBB######BBBBBB####
@@@@@@@@@@@@@@@@@@@@@@@@@@&PPGB&@@@@&@@@@@@@YG@BYGGP5?~!5@@@@@@@@@@@@@@@@@@@@@&BPGGB######BBBBBBB###
@@@@@@@@@@@@@@@@@@@@@@@@@@#55G#@@@@@@@@@@@@@?Y@@PJYPPJ!!Y&@@@@@@@@@@@@@@@@@@@@@#PPGBBB###BBBBBBBBB##
@@@@@@@@@@@@@@@@@@@@@@@@@@PY5PG#&&&&&&&#&&&&&@@&BYPPPY!~?#@@@@@@@@@@@@@@@@@@@@@@GPGGBBBBBBBBBBBBBB##
@@@@@@@@@@@@@@@@@&PJ??B@@&YY5P555PPGBB#&&&###G5JJY55P5?~7B@@@@@@@@@@@@@@@@@@@@@@#PGGGGBBBBBBBBBBB###
@@@@@@@@@@@@@@@@@5B#B5B@@#Y555J7!!777?????7!~~!7?J5PP5?!~5@@@@@@@@@@@@@@@@@@@@@@@BGGGGGBBBBBBBBBB###
@@@@@@@@@@@@@@@@5B@&YY&@@G555Y7~^^::^^~~~!!7?YPGGB#B5J?7!?B@@@@@@@@@@@@@@@@@@@@@@&GGGGGBBBBBBBBB####
@@@@@@@@@@@@@@@#Y@&!~P@&#PGP5J!^:...:^^~7J5G##&P?7YGJ!~~JJY#@@@@@@@@@@@@@@@@@@@@@@BGGGGGBBB#######&#
@@@@@@@@@@@@@@@&J&J!#@P^GPGGPJ!^:..^!7?5B&@&GYGBGPG#BGPB&&&@@@@@@@@@@@@@@@@@@@@@@@#GGGGGBB########&&
@@@@@@@@@@@@@@@@PJ?5@@5!PPPP5J7~~~~!?YB@@&GYJJ5B&&&@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#GGGGGBB###&##&&&&
@@@@@@@@@@@@@@@@@JJ?55BPPP5P5JJJY?7?YB@&GYJJ??JJJJ5PGB#&@@@@@@@@@@@@@@@@@@@@@@@@@@#GGGGGBB#&&&&&&@@&
@@@@@@@@@@@@@@@@@G^!~:~PPP555Y55YYJYG@#5YYJ?7!~~~~!!7JYPPGB#&@@@@@@@@@@@@@@@@@@@@@BGGGGGB#&&&&&&@@@@
@@@@@@@@@@@@@@@@@&PJJ?Y#P555YJ55YYYJG&Y?5PY7~~~~~!!7?YYYY5GB#&&@@@@@@@@@@@@@@@@@@@BGGGGGB#&&@@&&@@@@
@@@@@@@@@@@@@@@@@@@@@&@BP55YYJYPYY?75GJ5G&#BB###BBBB##&@@@@@@@@@@@@@@@@@@@@@@@@@@@BGGGGGB##&@@@&@@@@
@@@@@@@@@@@@@@@@@@@@@B#G555YY??YJ?7^:7?Y5Y7??77!~^~~~~!?JJY5PG#@@@@@@@@@@@@@@@@@@@&GGGGGBB#&@@&&@@@@
@@@@@@@@@@@@@@@@@@@@&G#GPPP5Y?7JJ?7^.:!!^.. .....:^~!?JJY5PB#@@@@@@@@@@@@@@@@@@@@GGGGGBB#&@&&@@@@@
@@@@@@@@@@@@@@@@@@@@#P#GPPPP5J7??JJ!^^~~:.. ...:..:^~!7J5555GB#&&@@@@@@@@@@@@@@@@@@#GGGGBB#&&&&&&@@@
@@@@@@@@@@@@@@@@@@@@BP##GGPP5J??7?Y?!~~^:.........:^~!7?JJJJ5PGB&&&@@@@@@@@@@@@@@@@&BGGGBB##&&&&&&@@
@@@@@@@@@@@@@@@@@@@@BP#&#BGP5YJ?77?J7~::::...:....:^!77??YJJ5PG####&@@@@@@@@@@@@@@@&BGGGBBB#####&&@@
@@@@@@@@@@@@@@@@@@@@BG@@&#BGPYJ??77?7~:::::..::.....::^^~!!7JYPPPPB#@@@@@@@@@@@@@@@@BGGGGBBB####&&@@
@@@@@@@@@@@@@@@@@@@&BB@&@&#BPYJ???77?!~::........ .....:^^~!?JJJY5G#@@@@@@@@@@@@@@@@#GGGBBBBBB##&&@@
@@@@@@@@@@@@@@@@@@@&BG&&&&##GPYJJ?????7!^::......:::...:^^~!?JJY5G#&@@@@@@@@@@@@@@@@&GGGGGBBBBBB#&&@
@@@@@@@@@@@@@@@@@@@&#B#&#&&##BP5YYJJYYYYJ7~~~~~~~^~!^:^~~!7?J5PPB&@@@@@@@@@@@@@@@@@@@#GGGGGBBBBB##&&
@@@@@@@@@@@@@@@@@@@@#BB&&#&&&&#GP555555GGGYJJ??JJ77????J5P5YPB##@@@@@@@@@@@@@@@@@@@@@@BGGGBBBBBBB#&&
@@@@@@@@@@@@@@#GBB#@&BGB&@&&@@&&#BGGGPGB#&&BGGGGGGGBBB##&&##@@@@@@@@@@@@@@@@@@@@@@@@@@@#BBBBBBBB##&&
@@@@@@@@@@@@@#?!YGB##BGGG#@@&@@@@@&&&&#&&@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&#BBB####&&@
@@@@@@@@@@@@@G!~~?PGGBBGGPG#@@&@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@##&&&&&&@
@@@@@@@@@@@@@@G7~~!YGGGGGGGGB&@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@&&&&&&&@#5~^^75GGGBB###&&@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&&@@@@
\* /\ */
//\\//\\//\\//\\//\\//\\//\\//\\//\\// utils and macros //\\//\\//\\//\\//\\//\\//\\//\\//\\//
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef __int128 lll;
#define vc vector
#define st first
#define nd second
#define pll pair<ll, ll>
#define sz(a) (ll)a.size()
#define all(a) a.begin(), a.end()
#define pub push_back
#define pob pop_back
void program();
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
program();
return 0;
}
ll INF = 1e18;
vc<ll> P9 = {998'244'353, 1'000'000'007, 1'000'000'009, 1'000'000'021, 1'000'000'033, 1'000'000'087, 1'000'000'093};
ll MOD = P9[0];
bool cont(ll mask, ll i) {
return (mask & (1ll << i)) != 0;
}
ll msb(ll mask) {
if (mask == 0)
return -1;
return 63 - __builtin_clzll(mask);
}
ll ceil(ll a, ll b) {
return (a + b - 1) / b;
}
ll f(ll x) {
x %= MOD;
if (x < 0)
x += MOD;
return x;
}
ll fme(ll a, ll b) {
ll ret = 1, x = a;
while (b > 0) {
if (b % 2 == 1)
ret = f(ret * x);
x = f(x * x);
b /= 2;
}
return ret;
}
ll inv(ll x) {
return fme(x, MOD - 2);
}
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\// solution //\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//
void program() {
ll V;
cin >> V;
vc<vc<ll>> g(V);
for (ll i = 0; i < V - 1; i++) {
ll v, w;
cin >> v >> w;
v--, w--;
g[v].pub(w);
g[w].pub(v);
}
vc<ll> a(V);
string str;
cin >> str;
for (ll v = 0; v < V; v++)
a[v] = str[v] == '1';
ll ans = 0;
vc<ll> dp(V);
function<void(ll, ll)> dfs = [&](ll v, ll p) {
dp[v] = -a[v];
for (ll w : g[v]) {
if (w == p)
continue;
dfs(w, v);
dp[v] += dp[w];
}
dp[v] = max(dp[v], a[v]);
ans = max(ans, dp[v]);
for (ll w : g[v])
if (w != p)
ans = max(ans, a[v] + dp[w]);
};
dfs(0, -1);
cout << ans << "\n";
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
