题意
构造一颗树使得满足计算方法的结果最小。
思路
考虑两棵树,一棵为题目中的询问构成的树$T1$,一棵为要构造的满足最终答案的树$T2$。从$T1$点权最小的点向外构造$T2$,在$T1$中倍增预处理出祖先,每次选取结果最小的作为对答案的贡献,在$T2$中让当前点连上这个祖先。由于点权最小的点为根,所以构造的过程中当前点始终满足点权大于父节点。
代码
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define DBG(x) cerr << #x << " = " << x << endl;using namespace std;typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const double eps = 1e-8;
const double pi = acos(-1.0);void file(){
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
}const int maxn = 5e5+5;
const int maxm = 1e6+5;int n;
int fa[maxn][25];
int tot,head[maxn];
LL minn=inf,pos,ans;
LL a[maxn];struct edgenode{
int to,next;
}edge[maxm];void addedge(int u,int v){
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
}void dfs(int x,int pre){
fa[x][0]=pre;
for(int i=1;i<=20;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
if(x != pre){
LL tmp=a[pre];
for(int i=1;i<=20;i++)tmp=min(tmp,a[fa[x][i]]*1LL*(i+1));
ans+=a[x]+tmp;
}
for(int i=head[x];i != -1;i=edge[i].next){
int v=edge[i].to;
if(v != pre)dfs(v,x);
}
}namespace BakuretsuMahou{
void Explosion(){
memset(head,-1,sizeof head);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%I64d",&a[i]);
if(a[i] < minn){
minn=a[i];
pos=i;
}
}
for(int i=1,x,y;i<=n-1;i++){
scanf("%d%d",&x,&y);
addedge(x,y);
addedge(y,x);
}
dfs(pos,pos);
printf("%I64d\n",ans);
}
}int main(){
//IOS
//file();
BakuretsuMahou::Explosion();
return 0;
}