제출 #460419

#제출 시각아이디문제언어결과실행 시간메모리
460419ak2006Putovanje (COCI20_putovanje)C++14
20 / 110
1095 ms55200 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
ll n = 2e5 + 5,TIMER;
vvvl adj(n);
vvi anc(n,vi(21));
vl pref(n);
vl in(n),out(n),weight1ToParent(n),weight2ToParent(n);
void dfs(int u,int p)
{
    in[u] = ++TIMER;
    anc[u][0] = p;
    for (int i = 1;i<=20;i++)anc[u][i] = anc[anc[u][i - 1]][i - 1];
    for (auto val:adj[u]){
        int v = val[0];
        if (v != p){
            weight1ToParent[v] = val[1];
            weight2ToParent[v] = val[2];
            dfs(v,u);
        }
    }
    out[u] = ++TIMER;
}
void dfs2(int u,int p)
{
    for (auto val:adj[u]){
        int v = val[0];
        if (v != p){
            dfs2(v,u);
            pref[u] += pref[v];
        }
    }
}
bool is_ancestor(int u,int v)
{
    return in[u] <= in[v] && out[u] >= out[v];
}
int LCA(int u,int v)
{
    if (in[u] > in[v])swap(u,v);
    if (is_ancestor(u,v))return u;
    for (int i = 20;i>=0;i--)
        if (!is_ancestor(anc[v][i],u))v = anc[v][i];
    return anc[v][0];
}
int main()
{
    setIO();
    cin>>n;
    for (int i = 1;i<=n - 1;i++){
        int u,v,w1,w2;
        cin>>u>>v>>w1>>w2;
        adj[u].pb({v,w1,w2});
        adj[v].pb({u,w1,w2});
    }
    dfs(1,1);
    for (int i = 1;i<=n - 1;i++){
        int u = i,v = i + 1;
        int l = LCA(u,v);
        while (u != l){
            pref[u]++;
            u = anc[u][0];
        }
        while (v != l){
            pref[v]++;
            v = anc[v][0];
        }
        // pref[u]++;
        // pref[v]++;
        // pref[l]--;
        // pref[anc[l][0]]--;
    }
    // dfs2(1,1);
    ll ans = 0;
    for (int i = 2;i<=n;i++)
        ans += min(pref[i] * weight1ToParent[i],weight2ToParent[i]);
    cout<<ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...