Submission #342844

#	Time	Username	Problem	Language	Result	Execution time	Memory
342844		limabeans	Sjekira (COCI20_sjekira)	C++17	110 / 110	62 ms	27904 KiB

sjekira

#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 = 1e6 + 5;


int n;
ll a[maxn];
vector<int> g[maxn];

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

    cin>>n;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }

    ll res = 0;
    
    for (int i=0; i<n-1; i++) {
	int u,v; cin>>u>>v;
	g[u].push_back(v);
	g[v].push_back(u);
	
	res += max(a[u],a[v]);
    }

    ll sum = 0;
    ll hi = 0;
    for (int i=1; i<=n; i++) {
	hi = max(hi,a[i]);
	sum += a[i];
    }

    res += sum;
    res -= hi;
    out(res);
    
    return 0;
}



// [1] it's optimal to always snip off an edge from the max node in the tree (swapping argument)
// sum over edges e { max(e.u, e.v) }

// [2] every node is eventually isolated and snipped off
// sum a[i]

// subtract max a[i] because it's contribution is entirely from [1]

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