#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
#define f first
#define s second
#define pii pair<int,int>
#define piii pair<int,pair<int,int>>
#define vii vector<vector<int>>
#define vi vector<int>
#define cd complex<double>
#define endl '\n'
//#define multipletest
using namespace std;
const int LIM=1e5;
const int INF = 1e18;
const string name="template";
int n,m;
int dp[LIM+5];
string s;
vector<int> adj[LIM+5];
int plant[LIM+5];
int ans=0;
void dfs(int u,int parent){
int sum=0;
for(auto v:adj[u]){
if(v==parent) continue;
dfs(v,u);
sum+=dp[v];
}
dp[u] = sum - plant[u];
dp[u]=max(dp[u],plant[u]);
for(auto v:adj[u]){
if(v==parent) continue;
ans=max(ans,dp[v] + plant[u]);
}
}
void solve(){
//CODE GOES HERE
cin>>n;
for(int i=0;i<n-1;++i){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
cin>>s;
for(int i=0;i<s.size();++i){
if(s[i]=='1'){
plant[i+1]=1;
}
}
dfs(1,0);
cout<<ans<<endl;
}
signed main(){
// freopen((name+".inp").c_str(),"r",stdin);
// freopen((name+".out").c_str(),"w",stdout);
// ifstream cin(".txt");
// ofstream cout(".txt");
//ifstream cin((name +".inp"));
//ofstream cout((name +".ans"));
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int test;
test=1;
#ifdef multipletest
cin>>test;
#endif
while(test--){
solve();
#ifdef DEBUG
cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl;
#endif
}
}
Compilation message
power.cpp: In function 'void solve()':
power.cpp:48:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i=0;i<s.size();++i){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
