Submission #1239268

#TimeUsernameProblemLanguageResultExecution timeMemory
1239268trantrungkeinPower Plant (JOI20_power)C++20
100 / 100
149 ms27036 KiB
#include <bits/stdc++.h>
 
#define fi           first 
#define si           second 
#define For(i,a,b)   for (int i = (a), _b =(b); i <= _b; ++i)
#define all(v)       v.begin(), v.end()
#define Unique(v)    v.erase(unique(all(v)), v.end())   
#define MASK(i)      (1LL << (i))
#define bit(i,n)     (((n)>>(i)) & 1)
#define Vii          vector<pair<int,int>>
#define setpr(x)     cout<<setprecision(x)<<fixed
#define Prior        priority_queue< pair<int,int> , Vii, greater<Pair> >
using namespace std;
 
const int Mod = 1E9 + 7;
const long long INF  = 4E18;
const int N = 2e5 + 1;
int n,dp[N],ans = 0,a[N];
vector<int> g[N];
void dfs(int u, int p)
{       
    int maxx = 0;
    for(int v : g[u]) if(v != p)
    {
        dfs(v,u);
        dp[u] += dp[v];
        maxx = max(dp[v],maxx);
    }
    if(a[u]) dp[u] = max(dp[u]-1,1);
    ans = max({dp[u],ans,maxx + a[u]});
}
signed main(){
    cin >> n;
    For(i,2,n)
    {
        int u,v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    string s;
    cin >> s;
    for(int i = 0; i < n; i++) a[i+1] = s[i]-'0';
    dfs(1,0);
    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...