#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll INF = 1e9;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
ll N; cin >> N;
if (N==0) {
cout << "1\n"; exit(0);
}
ll ans = 0;
vector<ll> adj[N];
vector<ll> fadj[N];
for (ll i=0;i<(N-1);i++) {
ll a,b; cin >> a >> b;
a--; b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
vector<bool> found;
vector<ll> radj;
for (ll i=0;i<N;i++) {
radj.push_back(-1);
found.push_back(0);
}
queue<ll> q0;
q0.push(0);
ll fdegL[N];
queue<ll> q1;
vector<ll> tpls;
while (!q0.empty()) {
ll x = q0.front(); q0.pop();
tpls.push_back(x);
for (ll y: adj[x]) {
if (y != radj[x]) {
fadj[x].push_back(y);
radj[y]=x;
q0.push(y);
}
}
fdegL[x]=fadj[x].size();
if (fdegL[x]==0) {
q1.push(x);
}
}
bool S[N];
string s1; cin >> s1;
for (ll i=0;i<N;i++) {
if (s1[i]=='1') {
S[i]=1;
} else {
assert(s1[i]=='0');
S[i]=0;
}
}
ll dp0[N]; //dp on: you know that it has to connect down; given that it
//does this, what is the max value?
ll dp1[N]; //does not connect down; what's the max value?
ll NUMFOUND=0;
/*while (!q1.empty()) {
ll x = q1.front(); q1.pop();
NUMFOUND++;
if (fadj[x].size()==0) {
dp0[x]=-INF;
dp1[x]=S[x];
} else {
dp1[x]=S[x];
ll mx=-INF; ll sm=0; //max and sum
for (ll y: fadj[x]) {
ll vy = max(dp1[y],dp0[y]);
mx = max(mx,vy);
sm += max(0LL,vy);
}
assert(mx!=(-INF));
//cout << "mx,sm,dp1="<<mx<<","<<sm<<","<<dp1[x]<<"\n";
ans = max(ans,dp1[x]+mx);
dp0[x]=sm-dp1[x];
ans = max(ans,dp0[x]);
}
if (radj[x]!=-1) {
fdegL[radj[x]]--;
if (fdegL[radj[x]]==0) {
q1.push(radj[x]);
}
}
}*/
for (ll i=(N-1);i>=0;i--) {
ll x = tpls[i];
NUMFOUND++;
if (fadj[x].size()==0) {
dp0[x]=-INF;
dp1[x]=S[x];
} else {
dp1[x]=S[x];
ll mx=-INF; ll sm=0; //max and sum
for (ll y: fadj[x]) {
ll vy = max(dp1[y],dp0[y]);
mx = max(mx,vy);
sm += max(0LL,vy);
}
assert(mx!=(-INF));
//cout << "mx,sm,dp1="<<mx<<","<<sm<<","<<dp1[x]<<"\n";
ans = max(ans,dp1[x]+mx);
dp0[x]=sm-dp1[x];
ans = max(ans,dp0[x]);
}
if (radj[x]!=-1) {
fdegL[radj[x]]--;
if (fdegL[radj[x]]==0) {
q1.push(radj[x]);
}
}
}
assert(NUMFOUND==N);
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
