推性质猜结论题

第一步转化，考虑把点的贡献加到边里：

$con=\sum (log_2(dis(a_u,a_b))\times min(a_u,a_v))+a_u+a_v$

然后一个结论：

一个点最多有一个相邻的点比它小

因为会连出一串，只能在唯一的最小值点结束

所以，以最小值为根，建出有根树，每个点的fa就是比它小的

整个树越往祖先权值越小

不妨再给边定向，令边的方向就是：$a_u>a_v,a_u->a_v$，

每个点只会连出去一条边，所以只用最小化：$(log_2(dis(a_u,a_v))+1)\times a_v$

发现，连出的边只会是往祖先连，否则dis会更大

而log_2是上去整，所以一定是$2^k$级祖先连过去最优！

注意如果不存在$2^k$级祖先，那么和$rt$也要试着连一连

 

#include
      
       #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')#define pb push_back#define solid const auto &#define enter cout<
       
        using namespace std;typedef long long ll;template
        
         il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
         
          il void output(T x){
    if(x/10)output(x/10);putchar(x%10+'0');}template
          
           il void ot(T x){
    if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
           
            il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{const int N=5e5+5;const ll inf=0x3f3f3f3f3f3f3f3f;ll ans;int n;struct node{ int nxt,to;}e[2*N];int hd[N],cnt;int a[N];void add(int x,int y){ e[++cnt].nxt=hd[x]; e[cnt].to=y; hd[x]=cnt;}int fa[N][20];int dfs(int x){ for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa[x][0]) continue; fa[y][0]=x; dfs(y); }}int main(){ rd(n); int rt=0; for(reg i=1;i<=n;++i) { rd(a[i]); if(!rt||a[i]