Submission #1091272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091272		pokmui9909	Designated Cities (JOI19_designated_cities)	C++17	16 / 100	157 ms	41804 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];

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);
    }
}

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] = *max_element(Val + 1, Val + N + 1);
    Dia(1, -1, 0);
    ll V = U;
    mxD = 0; Dia(V, -1, 0);
    Ans[2] = (mxD + Val[V]) / 2;

    cin >> Q;
    while(Q--){
        ll t; cin >> t;
        cout << Sum - Ans[t] << '\n';
    }
}

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