#include <bits/stdc++.h>
//ako ovaj vaso daso misli da me pobedjuje.....
using namespace std;
#define int long long
#define f first
#define s second
const int N = 2e5 + 69;
int n, mark[N], dp[N], up[N];
vector<int> g[N];
string s;
void dfs(int v, int p) {
int x = 0;
for (auto u : g[v]) {
if (u == p)
continue;
dfs(u, v);
x += (dp[u] > 0);
}
sort(g[v].begin(), g[v].end(), [&](int i, int j) {
return dp[i] > dp[j];
});
if (mark[v]) {
if (x < 2) {
dp[v] = 1;
for (auto u : g[v]) {
if (u == p)
continue;
dp[v] = dp[u];
if (dp[u] > 2) {
if (up[u] == 0)
dp[v]++;
up[v] = 1;
}
}
}
else {
for (auto u : g[v]) {
if (u == p)
continue;
dp[v] += dp[u] - 2 * up[u];
}
dp[v]--;
if (dp[v] <= 2 && up[v]) {
dp[v] = 1;
up[v] = 0;
}
}
}
else {
int mx = 0;
for (auto u : g[v]) {
if (u == p)
continue;
dp[v] += dp[u] - 2 * up[u];
mx = max(mx, dp[u]);
}
dp[v] = max(dp[v], mx);
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int tt = 1;
//cin >> tt;
while (tt--) {
cin >> n;
for (int i = 1;i <= n - 1;i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
cin >> s;
for (int i = 0;i < n;i++) {
if (s[i] == '1')
mark[i + 1] = 1;
}
dfs(1, 0);
int t = 1, p = 0;
while (g[t].size() <= 2 && t != -1) {
if (dp[t] == dp[1] && mark[t]) {
dp[1]++;
break;
}
int x = t;
t = -1;
for (auto u : g[x]) {
if (u == p)
continue;
p = t;
t = u;
}
}
cout << dp[1] << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
8796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
