问题描述

题面

思路

试想，如果没有父节点排在节点之前的限制，那么这个题目非常简单，需要将结点按照权值从大到小排列即可。加上了这个限制之后，如果权值最大的那个节点一旦满足了条件（父节点被排在了之前的某个位置），那么这个权值最大的节点一定要紧挨着这个父节点，即把这个权值最大的节点排在它所能排的最前面的位置。
因为对于这个节点如果不受限制应该排在第一位，而有了限制，在满足了限制之后也应把它尽可能地排在前面。所以它一定是挨着父节点的。
那么现在在最终的排列中我们确定了两个节点的前后相邻关系，将他们绑定在了一起。
试想如果保持这个相邻关系的同时去掉其他节点的限制，那么我们应该如何排列呢？
我们假设绑定在一起的两节点是a和b。现有一个另外的节点x，我们看两种排列xab,abx对最终的计算结果有什么影响。x_i+a_(i+1)+b_(i+2); a_i + b_(i+1) + x_(i+2)。
后者减去前者等于2x-(a+b)。即将x从ab之前挪到ab之后，ab各左移1位，结果减小a+b。x右移2位结果增加2x。
因此两者谁在前谁在后我们只需要比较a+b和2x即可，也可以比较(a+b)/2和x。
将这个定理进行一下推广，绑定在一起的不一定是两个节点，可以是一个更长的序列，与这个序列进行比较看谁放在前面的也可以是一个序列。设一个序列有n1个节点，第二个序列有n2个节点。那么我们比较两者谁放在前面的时候需要比较的是(n1个权值之和×n2)和(n2个权值之和×n1)。
即左移和右移产生的结果变化。当然也可以比较(n1个权值之和/n1)和(n2个权值之和/n2)。
我们可以再次进行推广，如果我们要排列的不是节点，而是许多序列的话，那么我们只需要计算每个序列权值的平均数（例如：n个节点的序列，要计算n个权值之和/n）,然后按照这个平均数从大到小排列即可使得计算结果最小。这样就可以让序列与节点有了一个统一的衡量值——平均数。
这样一来，我们就可以将上面的绑定两节点的操作看成是将问题规模缩小的操作，在帮定两节点的同时我们在树中也将两节点合并，变为一个节点，即将子节点的孩子变为父节点的孩子。
然后合并后的节点的权值是合并在这个节点中的所有节点的权值的平均数。我们成功的将问题规模减小了1。只需要不断这样做即可将问题缩减为只有一个节点。

代码

#include <bits/stdc++.h>
using namespace std;

struct node{
    int c,t,par;
    double v;
}t[1005];

int ans,n,r,a,b;

int getmin(){
    int id=0;
    double mt=0;
    for (int i=1;i<=n;++i){
        if (t[i].v>mt && i!=r){
            mt=t[i].v;
            id=i;
        }
    }
    return id;
}

int main(){
    cin>>n>>r;
    for (int i=1;i<=n;++i){
        scanf("%d",&t[i].c);
        t[i].t=1;
        t[i].v=t[i].c;
        ans+=t[i].c;
    }
    for (int i=1;i<=n-1;++i){
        scanf("%d %d",&a,&b);
        t[b].par=a;
    }
    for (int i=1;i<=n-1;++i){
        int now=getmin();
        int par=t[now].par;
        t[now].v=0;
        ans+=t[now].c*t[par].t;
        for (int j=1;j<=n;++j){
            if (t[j].par==now) t[j].par=par;
        }
        t[par].c+=t[now].c;
        t[par].t+=t[now].t;
        t[par].v=(double)t[par].c/t[par].t;
    }
    printf("%d\n",ans);
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/68/