Submission #930823

#	Time	Username	Problem	Language	Result	Execution time	Memory
930823		phoenix0423	Power Plant (JOI20_power)	C++17	100 / 100	110 ms	31376 KiB

power

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x;
const int maxn = 2e5 + 5;
const int INF = 1e18;
vector<int> adj[maxn];
int st[maxn], dp[maxn];
int ans = 0;

void dfs(int pos, int prev){
    int ttl = 0, ad = 0, mx = 0;
    for(auto x : adj[pos]){
        if(x == prev) continue;
        dfs(x, pos);
        if(dp[x] == 0) continue;
        mx = max(mx, dp[x]);
        ttl += dp[x];
        ad++;
    }
    ans = max(ans, mx + st[pos]);
    dp[pos] = max(ttl - st[pos], st[pos]);
    ans = max(ans, dp[pos]);
}

signed main(void){
    fastio;
    int n;
    cin>>n;
    for(int i = 0; i < n - 1; i++){
        int a, b;
        cin>>a>>b;
        a--, b--;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    string s;
    cin>>s;
    for(int i = 0; i < n; i++) st[i] = (s[i] == '1');
    dfs(0, -1);
    cout<<ans<<"\n";
}

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