CF1088F Ehab and a weird weight formula

推性质猜结论题

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

$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<bits/stdc++.h>

#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<<endl

#define pii pair<int,int>

using namespace std;

typedef long long ll;

template<class T>il void rd(T &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

template<class T>il void output(T x){if(x/)output(x/);putchar(x%+'');}

template<class T>il void ot(T x){if(x<) putchar('-'),x=-x;output(x);putchar(' ');}

template<class T>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+;

const ll inf=0x3f3f3f3f3f3f3f3f;

ll ans;

int n;

struct node{

    int nxt,to;

}e[*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][];

int dfs(int x){

    for(reg i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==fa[x][]) continue;

        fa[y][]=x;

        dfs(y);

    }

}

int main(){

    rd(n);

    int rt=;

    for(reg i=;i<=n;++i) {

        rd(a[i]);

        if(!rt||a[i]<a[rt]) rt=i;

    }

    int x,y;

    for(reg i=;i<n;++i){

        rd(x);rd(y);add(x,y);add(y,x);

    }

    dfs(rt);

    for(reg j=;j<=;++j){

        for(reg i=;i<=n;++i){

            fa[i][j]=fa[fa[i][j-]][j-];

        }

    }

    for(reg i=;i<=n;++i){

        ll mi=inf;

        if(i==rt) continue;

        for(reg j=;j<=;++j){

            if(!fa[i][j]) {

                mi=min(mi,(ll)(j+)*a[rt]);

                break;

            }

            mi=min(mi,(ll)(j+)*a[fa[i][j]]);

        }

        ans+=mi+a[i];

    }

    ot(ans);

    return ;

}

}

signed main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

*/

巴特西

CF1088F Ehab and a weird weight formula

最新文章

热门文章