Codeforces Round #525 (Div. 2) F. Ehab and a weird weight formula

F. Ehab and a weird weight formula

题目链接：https://codeforces.com/contest/1088/problem/F

题意：

给出一颗点有权值的树，满足只有一个点的权值最小，然后除开这个点，每个点都有一个权值比它更小的点与之相邻。

然后要求你重构这颗树，满足点权及边权和最小。

点权计算方法: a_u = a_u*num(num为与之相邻边的个数);

边权计算方法: e{u,v}，w_e = dis(u,v)*min(a_u,a_v) (dis(u,v)为given tree中u和v的距离)。

题解：

首先我们若以权值最小的点为根，我们会发现这棵树越往下，点的权值就会越大。

假定我们随便选择一对{u,v}，那么对答案的贡献就是 a_u+a_v+log2(dis(u,v))*min(a_u,a_v)，要让权值最小，假设我们先固定u来寻找v，由于受到v的权值和dis(u,v)的限制，所以我们可以考虑采用贪心的思想，对于一个点u，我们尽可能地向其祖先找点v，同时算一下距离。最终会找到一个最优解。

但是直接枚举太慢了，发现首先我们可以优化一下，就是每次往上找2的倍数个结点（因为题目中是log2(dis(u,v)) ）。

由于a_v<a_u，所以每对{u,v}对答案的贡献就是a_u+(log2(dis(u,v))+1)*a_v。

最终总复杂度是O(nlogn)。

代码如下：

#include <bits/stdc++.h>

#define INF 999999999999

using namespace std;

typedef long long ll ;

const int N =5e5+ ;

int a[N],dp[][N];

int n,st;

vector <int> vec[N];

ll ans;

void dfs(int u,int pa){

    dp[][u]=pa;

    for(int i=;i<;i++){

        if(dp[i-][u]==-) break ;

        dp[i][u]=dp[i-][dp[i-][u]];

    }

    ll minx = INF;

    int i;

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

        if(dp[i][u]==-) break ;

        minx=min((ll)(i+)*a[dp[i][u]]+a[u],minx);

    }

    minx=min((ll)(i+)*a[st]+a[u],minx);

    if(u!=st) ans+=minx;

    for(auto v:vec[u]){

        if(v!=pa) dfs(v,u);

    }

}

int main(){

    scanf("%d",&n);

    st=;a[]=1e9+;

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

        scanf("%d",&a[i]);

        if(a[i]<a[st])st=i;

    }

    for(int i=,u,v;i<n;i++){

        scanf("%d%d",&u,&v);

        vec[u].push_back(v);

        vec[v].push_back(u);

    }

    memset(dp,-,sizeof(dp));

    dfs(st,-);

    printf("%I64d",ans);

    return ;

}

巴特西

Codeforces Round #525 (Div. 2) F. Ehab and a weird weight formula

最新文章

热门文章