学步园

题意：

有一棵树，需要给其所有节点染色，每个点染色所需的时间是一样的都是1.给每个点染色，还有一个开销“当前时间×ci”，ci是每个节点的一个权值。 
染色还有另一个约束条件，要染一个点必须要先染好其父节点，所以第一个染的点是根节点。 

求最小开销。

解法：

小班课比较详细地给出了解法和证明。 
（以下已经把每个点看成一个点集，独立的一个点可看做只有一个元素的点集，每个点集中的点有顺序，并且需要依次连续地染色，也就是染完第一个点后，需要立刻依次染之后的点） 
每次找一个最大权值的非根点集，将它和它的父点集合并。新的点集的权值是（新点集中所有点的权值和）/（新点集中点的个数）。这里点集中的点有顺序，合并时，子点集的点放在父点集的点后面。 
进行上述步骤，直到只剩下一个根点集。这时候，根点集中点的顺序，就是染色的顺序。

证明：

(i)先看每个都是点的情况。给出一个结论：如果这棵树中有最大权值点x（非根），那么一旦x的父节点已经染色，就应该立刻染x。 
这比较好证：设x的父节点为y，染色顺序为ya...bx,a...b这一段是别的一些可以染的点。这个染色顺序的意思是说染完x的父节点y之后，先染了一些别的点，再染x。 
如果我们把b和x的染色顺序交换，显然是可行的，并且会更优：比较xb和bx，使用前者我们的收益（少掉的开销）是Cx-Cb，x少等了1的时间，b多等了1的时间。显然，收益Cx-Cb是正的，因为x的权值是当前最大的。这样我们也可以证，染完y之后应该立刻染x，所以可以把y和x合并成一个点集。 
(ii)现在看都看做点集的情况，证明合并后以平均权值作为新的权值是合理的。 
一个结论：如果这棵树中有最大平均权值点集X（非根），那么一旦X的父点集已经染色，就应该立刻染X。

这和(i)类似：设X的父子集Y，染色顺序YA...BX，A...B是别的一些可以染的点集。下证B和X染色顺序互换可以更优。设B的总权值为SB，点数为NB;X的为SX和NX。XB和BX比较，使用前者的收益是SX×NB- SB×NX，这相当与X中的每个点都少等待NB时间，而B中的每个点都多等了NX的时间。又因为X是最大平均权值点集，所以权值SX/NX>SB/NB，所以可以确保收益SX×NB-SB×NX是正的。

#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#define maxn 1005
using namespace std;
 
class node
{
    public:
        int value_sum;//点集中所有点的权值和
        int num;//点集中点的个数
        int father;
        int set_id;//所属点集编号
        bool is_setrep;//是不是点集的首个元素
        double value;//权值平均
        vector<int> in_set;//点集中其他点
        vector<int> son;//该点集的子点集
 
        node()
        {
            num = 1;
            father = -1;
            is_setrep = true;
        }
};
 
node no[maxn];
int seq[maxn] = {0};//最后的涂的顺序的序列
int c[maxn] = {0};//涂每个点的花费
 
int n = 0, r = 0;
 
void init()
{
    memset(no, 0, sizeof(no));
    for (int i = 1; i <= n; ++i)
    {
            no[i].num = 1;
            no[i].father = -1;
            no[i].is_setrep = true;
    }
}
 
//将编号为a的点集与其父点集合并
void union_node(int a)
{
    int fa = no[a].father;
    int son_num = no[a].son.size();
    //printf("sonnum: %d\n", son_num);
    no[fa].value_sum += no[a].value_sum;
    no[fa].num += no[a].num;
    no[fa].value = (double)(no[fa].value_sum) / no[fa].num;
    no[a].set_id = fa;
    no[a].is_setrep = false;
    no[fa].in_set.push_back(a);
    //printf("value: %f\n", no[fa].value);
    for (int i = 0; i < no[a].num - 1; ++i)
    {
        no[fa].in_set.push_back(no[a].in_set[i]);
        no[no[a].in_set[i]].set_id = fa;
    }
    for (int i = 0; i < son_num; ++i)
    {
        no[no[a].son[i]].father = fa;
        no[fa].son.push_back(no[a].son[i]);
    }
}
 
int main()
{
    while(true)
    {
        scanf("%d%d", &n, &r);
        init();
        if (n == 0)
            break;
        int tmp = 0;
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d", &tmp);
            c[i] = tmp;
            no[i].value = no[i].value_sum = tmp;
            no[i].set_id = i;
        }
 
        int tmp1 = 0, tmp2 = 0;
        for (int i = 0; i < n - 1; ++i)
        {
            scanf("%d%d", &tmp1, &tmp2);
            if(tmp1 == 0)
                break;
            no[tmp1].son.push_back(tmp2);
            no[tmp2].father = tmp1;
        }
 
        int cur_num = n;
        while(true)
        {
            if (cur_num == 1)
                break;
            double max_v = 0;
            int max_i = 0;
            for (int i = 1; i <= n; ++i)
            {
                //每次找不是根节点的最大权值子集与其父子集合并
                if (no[i].is_setrep && i != r && max_v < no[i].value)
                {
                    max_v = no[i].value;
                    max_i = i;
                }
            }
            //printf("%d\n", max_i);
            union_node(max_i);
 
            --cur_num;
        }
 
        seq[1] = c[r];
        for (int i = 0; i < n - 1; ++i)
        {
            seq[i + 2] = c[no[r].in_set[i]];
        }
 
        int ans = 0;
        for (int i = 1; i <= n; ++i)
        {
            ans += i*seq[i];
        }
        printf("%d\n", ans);
    }
    return 0;
}

所以这样合并没有问题。

所以这样合并没有问题。