#include<bits/stdc++.h>
#include<unordered_map>
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define trav(a,v) for(auto& a: v)
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
#define vi vector<int>
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const long long inf = 1e15;
using namespace std;
vector<vector<ll>> dp(1e6,vector<ll>(2,-inf));
vector<ll> parents(1e6);
vector<vector<ll>> children(1e6);
string s;
ll solve(ll cur,bool lit) {
if (children[cur].size() == 0) {
return s[cur-1] == '1';
}
if (dp[cur][lit] != -inf)return dp[cur][lit];
ll ans1=-inf;
ll ans2=-inf;
ll ans3 = 0;
ll ans4 = 0;
trav(a, children[cur]) {
ans1 = max(ans1, solve(a,lit));
}
trav(a, children[cur]) {
ans2 = max(ans2, solve(a, 1));
}
ll one = 1;
ll zero = 0;
if (s[cur - 1] == '1') {
if(lit)ans2 -= 1, ans1 -= 1;
}
ans1 = max(zero, ans1);
ans2 = max(one, ans2);
trav(a, children[cur]) {
ans3 += solve(a, 1);
}
trav(a, children[cur]) {
ans4 += solve(a, lit);
}
if (s[cur - 1] == '1') {
ans3--;
ans4--;
}
return dp[cur][lit] = max(max(ans1, ans2),max(ans3,ans4));
}
int main() {
cin.sync_with_stdio(false);
ll n;
cin >> n;
vector<vector<ll>> g(n + 1);
rep(i, 0, n-1) {
ll a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
cin >> s;
if (n == 1) {
cout << (s == "1" ? 1 : 0)<<endl;
}
else if (n == 2) {
ll ans = 0;
trav(a, s)ans += a == '1';
cout << ans << endl;
}
queue<ll> q;
vector<bool> isLeaf(n+1);
rep(i, 1, n + 1)if (g[i].size() == 1)isLeaf[i]=1;
ll root = -1;
rep(i, 1, n + 1)if (!isLeaf[i])root = i;
q.push(root);
vector<bool> visited(n + 1);
visited[root] = 1;
while (!q.empty()) {
ll cur = q.front();
q.pop();
trav(a, g[cur]) {
if (!visited[a]) {
parents[a] = cur;
children[cur].push_back(a);
visited[a] = 1;
q.push(a);
}
}
}
rep(i, 1, n + 1) {
if (isLeaf[i]) {
q.push(i);
}
}
parents[root] = -1;
cout << solve(root,0);
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
84 ms |
86368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
84 ms |
86368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
84 ms |
86368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
