제출 #479925

#제출 시각아이디문제언어결과실행 시간메모리
479925sam571128Fireworks (APIO16_fireworks)C++17
26 / 100
1 ms588 KiB
#include <bits/stdc++.h>
#include <bits/extc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 605, M = 305;
vector<pair<int,int>> adj[N];

int dp[N], to[N], deg[N], ans = 0;

__gnu_pbds::priority_queue<int> pq[N];

void dfs(int u, int p){
    for(auto [v,w] : adj[u]){
        if(v == p) continue;
        dfs(v,u);
        pq[u].join(pq[v]);
    }

    if(u==1) return;

    int l = 0, r = 0;

    if(deg[u]){
        while(--deg[u]){
            pq[u].pop();
        }

        r = pq[u].top();
        pq[u].pop();

        l = pq[u].top();
        pq[u].pop();
    }

    pq[u].push(l+to[u]);
    pq[u].push(r+to[u]);
}

signed main(){
    fastio
    int n,m;
    cin >> n >> m;
    for(int i = 2;i <= n;i++){
        int p,x;
        cin >> p >> x;
        to[i] = x;
        adj[p].push_back({i,x});
        adj[i].push_back({p,x});
        deg[p]++;
        ans += x;
    }
    for(int i = 1;i <= m;i++){
        int p,x;
        cin >> p >> x;
        to[n+i] = x;
        adj[p].push_back({i+n,x});
        adj[i+n].push_back({p,x});
        deg[p]++;
        ans += x;
    }

    dfs(1,-1);

    while(deg[1]--){
        pq[1].pop();
    }

    while(!pq[1].empty()){
        ans -= pq[1].top();
        pq[1].pop();
    }


    cout << ans << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...