#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200000;
int n;
ll dp[N][3];
string s;
vector<int> adj[N];
void dfs(int x, int pr) {
dp[x][0] = INT_MIN;
if(s[x] == '1')
dp[x][0] = 1;
ll val1 = INT_MIN, val2 = 0, val3 = 0;
if(s[x] == '1')
val1 = 1;
ll v2 = 0;
for(auto e : adj[x]) if(e != pr) {
dfs(e, x);
dp[x][0] = 1 + max(dp[x][0] - 1, dp[e][2]);
val2 += max(0LL, dp[e][1]);
v2 += max(0LL, dp[e][2]);
val3 = max(val3, dp[e][1]);
}
dp[x][1] = max(val1, val2 - (s[x] == '1'));
dp[x][1] = max(dp[x][1], val3);
dp[x][2] = val1;
dp[x][2] = max(dp[x][2], v2 - (s[x] == '1'));
dp[x][2] = max(dp[x][2], 0LL);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 0;i < n-1;i ++) {
int x, y; cin >> x >> y;
x --,y --;
adj[x].push_back(y);
adj[y].push_back(x);
}
cin >> s;
dfs(0, -1);
ll ans = 0;
for(int i = 0;i < n;i ++) {
cerr << dp[i][0] << ' ' << dp[i][1] << ' ' << dp[i][2] << '\n';
ans = max(ans, dp[i][0]);
ans = max(ans, dp[i][1]);
}
cout << ans << '\n';
}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200000;
int n;
ll dp[N][3];
string s;
vector<int> adj[N];
void dfs(int x, int pr) {
dp[x][0] = INT_MIN;
if(s[x] == '1')
dp[x][0] = 1;
ll val1 = INT_MIN, val2 = 0, val3 = 0;
if(s[x] == '1')
val1 = 1;
ll v2 = 0;
for(auto e : adj[x]) if(e != pr) {
dfs(e, x);
dp[x][0] = 1 + max(dp[x][0] - 1, dp[e][2]);
val2 += max(0LL, dp[e][1]);
v2 += max(0LL, dp[e][2]);
val3 = max(val3, dp[e][1]);
}
dp[x][1] = max(val1, val2 - (s[x] == '1'));
dp[x][1] = max(dp[x][1], val3);
dp[x][2] = val1;
dp[x][2] = max(dp[x][2], v2 - (s[x] == '1'));
dp[x][2] = max(dp[x][2], 0LL);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for(int i = 0;i < n-1;i ++) {
int x, y; cin >> x >> y;
x --,y --;
adj[x].push_back(y);
adj[y].push_back(x);
}
cin >> s;
dfs(0, -1);
ll ans = 0;
for(int i = 0;i < n;i ++) {
cerr << dp[i][0] << ' ' << dp[i][1] << ' ' << dp[i][2] << '\n';
ans = max(ans, dp[i][0]);
ans = max(ans, dp[i][1]);
}
cout << ans << '\n';
}
Compilation message
power.cpp:71:11: error: redefinition of 'const int N'
71 | const int N = 200000;
| ^
power.cpp:6:11: note: 'const int N' previously defined here
6 | const int N = 200000;
| ^
power.cpp:73:5: error: redefinition of 'int n'
73 | int n;
| ^
power.cpp:8:5: note: 'int n' previously declared here
8 | int n;
| ^
power.cpp:74:4: error: redefinition of 'll dp [200000][3]'
74 | ll dp[N][3];
| ^~
power.cpp:9:4: note: 'll dp [200000][3]' previously declared here
9 | ll dp[N][3];
| ^~
power.cpp:75:8: error: redefinition of 'std::string s'
75 | string s;
| ^
power.cpp:10:8: note: 'std::string s' previously declared here
10 | string s;
| ^
power.cpp:76:13: error: redefinition of 'std::vector<int> adj [200000]'
76 | vector<int> adj[N];
| ^~~
power.cpp:11:13: note: 'std::vector<int> adj [200000]' previously declared here
11 | vector<int> adj[N];
| ^~~
power.cpp:78:6: error: redefinition of 'void dfs(int, int)'
78 | void dfs(int x, int pr) {
| ^~~
power.cpp:13:6: note: 'void dfs(int, int)' previously defined here
13 | void dfs(int x, int pr) {
| ^~~
power.cpp:106:5: error: redefinition of 'int main()'
106 | int main() {
| ^~~~
power.cpp:41:5: note: 'int main()' previously defined here
41 | int main() {
| ^~~~
