Submission #763287

#	Time	Username	Problem	Language	Result	Execution time	Memory
763287		vjudge1	Power Plant (JOI20_power)	C++14	100 / 100	181 ms	27732 KiB

power

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<ll,ll>
const ll maxn=2e5+2;

vector <int> adj[maxn];

int dp[maxn];
int gen[maxn];
int sub[maxn];
int ans;

void dfs(int u, int pre){
    //cout<<u<<endl;
    int mx=0;
    int sum=0;
    for (int v: adj[u]){
        if (v!=u&&v!=pre){
            dfs(v,u);
            mx=max(mx,dp[v]);
            sum+=dp[v];
            sub[u]+=sub[v];
        }
    }
    dp[u]=max(gen[u],sum-gen[u]);
    ans=max(ans,max(dp[u],mx+gen[u]));
}
int main(){
    int n; cin>>n;
    for (int i=1;i<n;++i){
        int x,y; cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }   
    string s; cin>>s;
    for (int i=1;i<=n;++i){
        gen[i]=s[i-1]-'0';
    }
    //cout<<s;
    dfs(1,1);
    //for (int i=1;i<=n;++i) cout<<i<<" "<<dp[i]<<"\n";
    cout<<ans;
}

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