CF1088F Ehab and a weird weight formula

ゞ浴缸里的玫瑰 2021-11-13 15:38 203阅读 0赞

[CF1088F Ehab and a weird weight formula][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$也要试着连一连

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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=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<class T>il void output(T x){
         if(x/10)output(x/10);putchar(x%10+'0');}
    template<class T>il void ot(T x){
         if(x<0) 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+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]<a[rt]) rt=i;
        }
        int x,y;
        for(reg i=1;i<n;++i){
            rd(x);rd(y);add(x,y);add(y,x);
        }
        dfs(rt);
        for(reg j=1;j<=19;++j){
            for(reg i=1;i<=n;++i){
                fa[i][j]=fa[fa[i][j-1]][j-1];
            }
        }
        for(reg i=1;i<=n;++i){
            ll mi=inf;
            if(i==rt) continue;
            for(reg j=0;j<=19;++j){
                if(!fa[i][j]) {
                    mi=min(mi,(ll)(j+1)*a[rt]);
                    break;
                }
                mi=min(mi,(ll)(j+1)*a[fa[i][j]]);
            }
            ans+=mi+a[i];
        }
        ot(ans);
        return 0;
    }
    
    }
    signed main(){
        Miracle::main();
        return 0;
    }
    
    /*
       Author: *Miracle*
    */

转载于:https://www.cnblogs.com/Miracevin/p/10836925.html

[CF1088F_Ehab and a weird weight formula]: https://www.luogu.org/problemnew/show/CF1088F
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211113/bccd374e2bc64f73a3a36f821c8fb147.png