Submission #854476

#	Time	Username	Problem	Language	Result	Execution time	Memory
854476		vjudge1	Sjekira (COCI20_sjekira)	C++17	0 / 110	31 ms	14060 KiB

sjekira

#pragma GCC optimize("unroll-loops,Ofast,O3")
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define spc << " " <<
#define endl "\n"
#define all(x) x.begin(), x.end()
#define ll long long
#define int long long
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define st first
#define nd second
#define inf 1000000009
#define MOD 1000000007
#define lim 100005
using namespace std;



vi edges[lim];
int maxi[lim], val[lim], chop[lim], par[lim];
int ans=0;

ii rang[lim];
int timey=0;
void tour(int node){
    timey++;
    rang[node] = {timey,timey};
    for(auto i:edges[node]){
        if(i==par[node]) continue;
        tour(i);
        rang[node].nd = rang[i].nd;
    }
}



void dfs(int node){
    maxi[node] = val[node];
    for(auto i:edges[node]){
        if(i==par[node]) continue;
        par[i]=node;
        dfs(i);
        maxi[node] = max(maxi[node], maxi[i]);
    }
}

void calc(int node){
    chop[node]=1;
    for(auto i:edges[node]){
        if(chop[i] || i==par[node]) continue;
        ans += val[node] + maxi[i];
        calc(i);
    }
}





void solve(){
    int n; cin >> n;
    vii next(n);
    for(int i=1; i<=n; i++){
        chop[i]=0;

        int a; cin >> a;
        val[i]=a;
        next[i-1] = {a, i};
    }
    sort(all(next), greater<ii>());

    for(int i=1; i<n; i++){
        int a,b; cin >> a >> b;
        edges[a].pb(b);
        edges[b].pb(a);
    }
    par[1]=0;
    dfs(1);



    tour(1);
    int ptr=0;
    int wow[n+1];
    for(int i=0; i<n-1; i++){
        ii cur = next[i];
        while(ptr<n && rang[next[ptr].nd].st>=rang[cur.nd].st && rang[next[ptr].nd].st<=rang[cur.nd].nd) ptr++;
        if(ptr>=n) break;
        wow[cur.nd] = next[ptr].st;
    }


    for(int j=0; j<n; j++){
        ii cur = next[j];
        if(cur.nd==1){
            for(auto i:edges[1]){
                if(chop[i]==0){
                    ans += maxi[i] + val[1];
                    calc(i);
                }
            }
            break;
        }

        if(chop[cur.nd]==0){
            ans += cur.st + wow[cur.nd];
            calc(cur.nd);
        }
    }
    cout << ans << endl;
}



signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    #ifdef Local
    freopen("in","r",stdin);
    freopen("out","w",stdout);
    #endif

    ll t=1;
    //cin >> t;
    while(t--) solve();
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60