#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID ((l+r)/2)
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;
#define EPS 1e-6
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto v : a)
int t, n;
vi a, b;
vector<vi> adj;
string x;
int cnt[300000];
int dfsc(int s, int p=-1){
cnt[s] = (x[s-1]=='1');
FOA(v,adj[s]) if(v!=p) cnt[s] += dfsc(v,s);
return cnt[s];
}
int dp[300000];
int dfs(int s, int p=-1){
if(dp[s]!=-1) return dp[s];
int ans2=0;
if(x[s-1]=='1') ans2 = 1;
int ans3 = 0;
if(x[s-1]=='1') ans3--;
FOA(v, adj[s]){
if(v==p) continue;
//cout<<s<<" going to "<<v<<endl;
//if(x[s-1]=='1') ans2 = max(ans2, 1+dfs(v,s));
ans3 += dfs(v,s);
}
ans2 = max(ans2, ans3);
//cout<<s<<" "<<prev<<" "<<ans2<<" "<<ans3<<endl;
dp[s] = ans2;
//cout<<s<<" "<<dp[s]<<endl;
return ans2;
}
int anss[300000];
int ans(int s, int p=-1){
int ans2=0;
int ans3 = 0;
if(x[s-1]=='1') ans3--;
FOA(v, adj[s]){
if(v==p) continue;
//cout<<s<<" going to "<<v<<endl;
if(x[s-1]=='1') ans2 = max(ans2, 1+dfs(v));
ans3 += dfs(v);
}
ans2 = max(ans2, ans3);
anss[s] = ans2;
//cout<<s<<" "<<ans2<<endl;
//cout<<s<<" "<<prev<<" "<<ans2<<" "<<ans3<<endl;
return ans2;
}
int main(){
cin>>n;
adj.assign(n+1, vi());
FOR(i,n+1) dp[i] = -1;
FOR(i,n-1){
int a, b;
cin>>a>>b;
adj[a].push_back(b);
adj[b].push_back(a);
}
cin>>x;
dfsc(1);
dfs(1);
int xx = ans(1);
FORi(i,1,n+1){
xx = max(xx, anss[(i)]);
//cout<<i<<" "<<ans(i)<<endl;
}
cout<<xx<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
