Submission #1204317

#TimeUsernameProblemLanguageResultExecution timeMemory
1204317vicvicPower Plant (JOI20_power)C++20
100 / 100
141 ms26256 KiB
#include <bits/stdc++.h>

using namespace std;
const int NMAX=2e5;
int n, dp[NMAX+5], mx=0;
vector <int> vec[NMAX+5];
string input;
void dfs (int nod, int tatal=0)
{
    int s=0, mxc=0;
    for (auto adj : vec[nod])
    {
        if (adj==tatal)
            continue;
        dfs (adj, nod);
        if (dp[adj]>mxc)
        {
            mxc=dp[adj];
        }
        dp[nod]+=dp[adj];
    }
    dp[nod]-=(input[nod]-'0');
    dp[nod]=max (dp[nod], input[nod]-'0');
    mx=max (mx, max (mxc+input[nod]-'0', dp[nod]));
}
int main ()
{
    cin >> n;
    for (int i=1;i<n;i++)
    {
        int x, y;
        cin >> x >> y;
        vec[x].push_back (y);
        vec[y].push_back (x);
    }
    cin >> input;
    input='#'+input;
    dfs (1);
    cout << mx;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...