#include<bits/stdc++.h>
using namespace std;
#define taskname "template"
#define ll long long
#define ld double
#define fi first
#define se second
#define vi vector<int>
#define pii pair<int,int>
#define vii vector<pii>
#define vvi vector<vi>
#define pb push_back
#define eb emplace_back
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int MN=2e5+5;
int n;
int a,b;
string s;
vi son[MN];
int color[MN];//on or off
bool check[MN];
int ans;
void bfs(int here){
int best=0;
queue<int> q;
q.push(here);
while(!q.empty()){
int u=q.front(); q.pop();
if(check[u]) continue;
check[u]=true; int cnt=color[u];
for(int v:son[u]){
if(check[v]) continue;
cnt+=color[v]; q.push(v);
}
best=max(best,cnt-(color[u]<<1));
}
if(color[here]) --best;
ans+=max(0,best);
// cout<<max(0,best-1)<<'\n';
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
/*
freopen(taskname".inp","r",stdin);
freopen(taskname".out","w",stdout);
*/
cin>>n;
check[n]=false;
for(int i=1;i<n;++i){
check[i]=false;
cin>>a>>b;
son[a].eb(b); son[b].eb(a);
}
cin>>s;
for(int i=0;i<n;++i){
color[i+1]=s[i]-'0';
}
int root=-1,max1=0;
for(int i=1;i<=n;++i){
int cnt=color[i];
for(int v:son[i]){
cnt+=color[v];
}
// cout<<"Case "<<i<<": "<<cnt<<'\n';
if(cnt>max1){
max1=cnt; root=i;
}
}
ans=max1-(color[root]<<1);
// cout<<ans<<'\n';
check[root]=true;
for(int v:son[root]){
// cout<<"Case "<<v<<": ";
bfs(v);
}
cout<<ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
