제출 #545533

#제출 시각아이디문제언어결과실행 시간메모리
545533AlperenTPutovanje (COCI20_putovanje)C++17
110 / 110
206 ms37692 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5, K = 20;

long long n, a, b, c1, c2, ans, cnt[N], binlift[N][K], depth[N];

struct Edge{
    long long b, c1, c2;
};

vector<Edge> tree[N];

void dfs(int v, int p){
    binlift[v][0] = p;
    for(int i = 1; i < K; i++) binlift[v][i] = binlift[binlift[v][i - 1]][i - 1];

    depth[v] = depth[p] + 1;

    for(auto e : tree[v]){
        if(e.b != p){
            dfs(e.b, v);
        }
    }
}

int lca(int a, int b){
    if(depth[b] > depth[a]) swap(a, b);

    for(int i = K - 1; i >= 0; i--) if(depth[binlift[a][i]] >= depth[b]) a = binlift[a][i];

    if(a == b) return a;

    for(int i = K - 1; i >= 0; i--){
        if(binlift[a][i] != binlift[b][i]){
            a = binlift[a][i], b = binlift[b][i];
        }
    }

    return binlift[a][0];
}

void dfs2(int v, int p){
    for(auto e : tree[v]){
        if(e.b != p){
            dfs2(e.b, v);

            ans += min(e.c1 * cnt[e.b], e.c2);

            cnt[v] += cnt[e.b];
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);

    cin >> n;

    for(int i = 1; i <= n - 1; i++){
        cin >> a >> b >> c1 >> c2;

        tree[a].push_back({b, c1, c2});
        tree[b].push_back({a, c1, c2});
    }

    dfs(1, 0);

    cnt[1]--, cnt[2]++;

    for(int i = 2; i <= n - 1; i++){
        int c = lca(i, i + 1);

        cnt[c] -= 2;

        cnt[i]++, cnt[i + 1]++;
    }

    dfs2(1, 0);

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