Submission #763189

#	Time	Username	Problem	Language	Result	Execution time	Memory
763189		huutuan	Power Plant (JOI20_power)	C++14	100 / 100	142 ms	25000 KiB

power

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

const int N=2e5+1;
int n, a[N], f[N][2];
vector<int> g[N];

void dfs(int u, int p){
    for (int v:g[u]) if (v!=p) dfs(v, u);
    int m=0;
    for (int v:g[u]) if (v!=p){
        f[u][0]+=f[v][1];
        m=max(m, f[v][1]);
    }
    int x=f[u][0]-a[u];
    f[u][0]=max(x, a[u]+m);
    f[u][1]=max(x, a[u]);
}

void solve(int tc){
    // cout << "Case #" << tc << ": ";
    cin >> n;
    for (int i=1; i<n; ++i){
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for (int i=1; i<=n; ++i){
        char c; cin >> c;
        a[i]=c-'0';
    }
    dfs(1, 1);
    int ans=0;
    for (int i=1; i<=n; ++i) ans=max(ans, f[i][0]);
    cout << ans;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int ntests=1;
    // cin >> ntests;
    for (int i=1; i<=ntests; ++i) solve(i);
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53