Submission #1232876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232876		letienbinh_812	Designated Cities (JOI19_designated_cities)	C++20	100 / 100	330 ms	68104 KiB

designated_cities

#include<bits/stdc++.h>
#define N 1000000
#define inf int(1e9+7)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<long long, int> li;
typedef pair<long long, li> loli;
// loli
loli gspvhcute;
//:333


const int M = 1e9+7;
int n,q;
ll sum;
struct edge{
    int v,w1,w2;
    edge(int x1, int x2, int x3): v(x1), w1(x2), w2(x3){}
};
vector<edge> adj[N+3];

ll dp[N+3];
array<ll,2> dp1[N+3];
array<ll,3> dp2[N+3];
ll ans[N+3];

void dfs(int u, int par){
    for(auto e:adj[u]){
        int v = e.v,
            w1 = e.w1,
            w2 = e.w2;
        if(v==par) continue;
        dfs(v,u);
        dp[u] += dp[v] + w2;
    }
    dp1[u] = {dp[u],u};
    dp2[u] = {0,u,u};
    for(auto e:adj[u]){
        int v = e.v,
            w1 = e.w1,
            w2 = e.w2;
        if(v==par) continue;

        ll rau_ria = dp[u] - dp[v] - w2;

        dp2[u] = max(dp2[u], array<ll,3>({dp[u] - dp[v] + w1 + dp1[v][0],   u, dp1[v][1]}));
        dp2[u] = max(dp2[u], array<ll,3>({dp1[u][0] - dp[v] + w1 + dp1[v][0], dp1[u][1], dp1[v][1]}));
        dp2[u] = max(dp2[u], array<ll,3>({dp2[v][0] + (dp[u] - dp[v] - w2) + w1, dp2[v][1], dp2[v][2]}));

        dp1[u] = max(dp1[u], array<ll,2>({dp[u] - dp[v] + w1 + dp1[v][0], dp1[v][1]}));
    }
}

void reroot(int u, int par, ll cur){
    ans[1] = min(ans[1], sum - cur);
    for(auto e:adj[u]){
        int v = e.v,
            w1 = e.w1,
            w2 = e.w2;
        if(v==par) continue;
        reroot(v,u, cur - w2 + w1);
    }
}
priority_queue<ll,vector<ll>> qQ;
ll dfs_greedy(int u, int par){
    if(u==dp2[1][2]) return 1e18;
    vector<ll> vec;


    for(auto e:adj[u]){
        int v = e.v,
            w1 = e.w1,
            w2 = e.w2;
        if(v==par) continue;
        vec.pb(dfs_greedy(v,u) + w1);
    }
    int pos = max_element(all(vec)) - vec.begin();
    for(int i=0; i<vec.size(); i++){
        if(i!=pos)
            qQ.push(vec[i]);
        else
            qQ.push(0);
    }
    if(vec.empty()) return 0;
    return vec[pos];
}

void Solve(){
    dfs(1,0);
    ans[2] = sum - dp2[1][0];
//    cout << dp1[1][0] << " " << dp2[1][0] << endl;
    ans[1] = 1e18;
    reroot(1,0,dp[1]);

    dfs_greedy(dp2[1][1],0);

    for(int i=3; i<=n; i++){
        ans[i] = ans[i-1] - qQ.top();
        qQ.pop();
    }
    cin >> q;
    for(int x,i=1; i<=q; i++){
        cin >> x;
        cout << ans[x] << "\n";
    }
}

void Inp(){
    cin >> n;
    for(int u,v,a,b,i=1; i<n; i++){
        cin >> u >> v >> a >> b;
        adj[u].pb(edge(v,a,b));
        adj[v].pb(edge(u,b,a));
        sum += a+b;
    }
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//    freopen(".inp","r",stdin);
//    freopen(".out","w",stdout);
    int T=1;
//    cin >> T;
    while(T--){
    Inp();
    Solve();
    }
}
//-----YEU CODE HON CRUSH-----//

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