Submission #1153972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153972		i271828	Sjekira (COCI20_sjekira)	C++20	40 / 110	1097 ms	12612 KiB

sjekira

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;

const int MAX=100005;

int N=3;
vector<int> adj[MAX]={};
int A[MAX]={1,2,3};

bool vis[MAX];

int dfs_max(int i,int p){
	int ans=i;
	for (auto x:adj[i]){
		if (x==p||vis[x]) continue;
		int y=dfs_max(x,i);
		if (A[y]>A[ans]) ans=y;
	}
	return ans;
}

pair<ll,int> calc(int i){
	ll ans=0;
	int max_i=dfs_max(i,-1);
	//cout<<max_i<<'\n';
	vis[max_i]=true;
	
	for (auto x:adj[max_i]){
		if (vis[x]) continue;
		ans+=A[max_i];
		auto y=calc(x);
		ans+=A[y.second];
		//cout<<ans<<' '<<y<<'a'<<'\n';
		ans+=y.first;
	}
	
	return {ans,max_i};
}

int main(){
	cin>>N;
	for (int i=0;i<N;i++) cin>>A[i];
	for (int i=0;i<N-1;i++){
		int a,b;
		cin>>a>>b;
		a--,b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	cout<<calc(0).first;
}

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