Submission #344924

#TimeUsernameProblemLanguageResultExecution timeMemory
344924limabeansPutovanje (COCI20_putovanje)C++17
0 / 110
195 ms27116 KiB
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;




const int maxn = 2e5 + 10;
const int LOG = 18;

int n;
pair<ll,ll> edge[maxn];
vector<pair<int,int>> g[maxn];


int dep[maxn];
int par[LOG+1][maxn];

void dfs(int at, int p) {
    for (int i=1; i<LOG; i++) {
	par[i][at] = par[i-1][par[i-1][at]];
    }
    
    for (auto ed: g[at]) {
	int to = ed.second;
	if (to == p) continue;
	dep[to]=1+dep[at];
	par[0][to]=at;
	dfs(to,at);
    }
}

ll dp[maxn];

int lca(int u, int v) {
    if (dep[u]<dep[v]) swap(u,v);
    int dx = dep[u]-dep[v];
    for (int i=0; i<LOG; i++) {
	if (dx>>i&1) {
	    u = par[i][u];
	}
    }

    if (u==v) return u;

    for (int i=LOG-1; i>=0; i--) {
	if (par[i][u] != par[i][v]) {
	    u = par[i][u];
	    v = par[i][v];
	}
    }

    return par[0][u];
}


ll edUsage[maxn];

void dfs2(int at, int p) {
    int edId = -1;
    for (auto ed: g[at]) {
	int to = ed.second;
	if (to==p) {
	    edId = ed.first;
	} else {
	    dfs2(to, at);
	}
    }

    if (~edId) {
	edUsage[edId] += dp[at];
	dp[p] += dp[at];
    }
}

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

    cin>>n;
    for (int i=0; i<n-1; i++) {
	int u,v; cin>>u>>v;
	int c0,c1;
	cin>>c0>>c1;
	g[u].push_back({i,v});
	g[v].push_back({i,u});
	edge[i] = {c0,c1};
    }

    dfs(1, 0);

    for (int i=1; i<n; i++) {
	int j=i+1;
	int mid = lca(i,j);
	dp[i]++;
	dp[j]++;
	dp[mid]--;
    }

    dfs2(1, 0);


    ll res = 0;

    for (int i=0; i<n-1; i++) {
	res += min(edge[i].second, edUsage[i]*edge[i].first);
    }


    cout<<res<<endl;
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...