Submission #1091280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091280		pokmui9909	Designated Cities (JOI19_designated_cities)	C++17	100 / 100	234 ms	63824 KiB

designated_cities

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define x first
#define y second

struct Edge{
    ll v, a, b;
};
vector<Edge> T[200005], C[200005];
ll N, Q, Sum = 0, Ans[200005], Val[200005], P[200005];
pair<ll, ll> dp[200005];

void cal1(ll u, ll p){
    for(auto e : T[u]){
        if(e.v == p) continue;
        Val[1] += e.b;
        cal1(e.v, u);
    }
}
void cal2(ll u, ll p){
    for(auto e : T[u]){
        if(e.v == p) continue;
        Val[e.v] = Val[u] - e.b + e.a;
        cal2(e.v, u);
    }
}
ll mxD = 0, U = 1;
void Dia(ll u, ll p, ll d){
    if(mxD < d + Val[u]){
        mxD = d + Val[u], U = u;
    }
    for(auto e : T[u]){
        if(e.v == p) continue;
        Dia(e.v, u, d + e.a + e.b);
    }
}

ll F = 0;
void cal3(ll u, ll p){
    P[u] = p, dp[u] = {0, u};
    for(auto e : T[u]){
        if(e.v == p) continue;
        cal3(e.v, u);
        dp[u] = max(dp[u], {dp[e.v].x + e.a, dp[e.v].y});
        F += e.b;
    }
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);

    cin >> N;
    for(ll i = 1; i < N; i++){
        ll u, v, a, b; cin >> u >> v >> a >> b;
        T[u].push_back({v, a, b}); T[v].push_back({u, b, a});
        Sum += a + b;
    }
    cal1(1, -1); cal2(1, -1);
    Ans[1] = Sum - *max_element(Val + 1, Val + N + 1);
    Dia(1, -1, 0);
    cal3(U, -1);
    priority_queue<pair<ll, ll>> PQ;
    PQ.push({dp[U].x, U});
    for(ll i = 2; i <= N; i++){
        if(i >= 3) Ans[i] = Ans[i - 1];
        if(PQ.empty()) continue;
        Ans[i] += PQ.top().x;
        ll r = PQ.top().y; PQ.pop();
        ll u = dp[r].y, pv = 0;
        while(1){
            for(auto e : T[u]){
                if(e.v == P[u] || e.v == pv) continue;
                PQ.push({e.a + dp[e.v].x, e.v});
            }
            if(u == r) break;
            pv = u, u = P[u];
        }
    }
    cin >> Q;
    while(Q--){
        ll t; cin >> t;
        cout << (t == 1 ? Ans[t] : Sum - Ans[t] - F) << '\n';
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44