locusxt

## 题意：

Color a Tree
 Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 6811 Accepted: 2318

Description

Bob is very interested in the data structure of a tree. A tree is a directed graph in which a special node is singled out, called the "root" of the tree, and there is a unique path from the root to each of the other nodes.

Bob intends to color all the nodes of a tree with a pen. A tree has N nodes, these nodes are numbered 1, 2, ..., N. Suppose coloring a node takes 1 unit of time, and after finishing coloring one node, he is allowed to color another. Additionally, he is allowed to color a node only when its father node has been colored. Obviously, Bob is only allowed to color the root in the first try.

Each node has a "coloring cost factor", Ci. The coloring cost of each node depends both on Ci and the time at which Bob finishes the coloring of this node. At the beginning, the time is set to 0. If the finishing time of coloring node i is Fi, then the coloring cost of node i is Ci * Fi.

For example, a tree with five nodes is shown in Figure-1. The coloring cost factors of each node are 1, 2, 1, 2 and 4. Bob can color the tree in the order 1, 3, 5, 2, 4, with the minimum total coloring cost of 33.

Given a tree and the coloring cost factor of each node, please help Bob to find the minimum possible total coloring cost for coloring all the nodes.

Input

The input consists of several test cases. The first line of each case contains two integers N and R (1 <= N <= 1000, 1 <= R <= N), where N is the number of nodes in the tree and R is the node number of the root node. The second line contains N integers, the i-th of which is Ci (1 <= Ci <= 500), the coloring cost factor of node i. Each of the next N-1 lines contains two space-separated node numbers V1 and V2, which are the endpoints of an edge in the tree, denoting that V1 is the father node of V2. No edge will be listed twice, and all edges will be listed.

A test case of N = 0 and R = 0 indicates the end of input, and should not be processed.

Output

For each test case, output a line containing the minimum total coloring cost required for Bob to color all the nodes.

Sample Input

``````5 1
1 2 1 2 4
1 2
1 3
2 4
3 5
0 0``````

Sample Output

``33``

Source

[Submit]   [Go Back]   [Status]   [Discuss]

## 解法：

（以下已经把每个点看成一个点集，独立的一个点可看做只有一个元素的点集，每个点集中的点有顺序，并且需要依次连续地染色，也就是染完第一个点后，需要立刻依次染之后的点）

## 证明：

(i)先看每个都是点的情况。给出一个结论：如果这棵树中有最大权值点x（非根），那么一旦x的父节点已经染色，就应该立刻染x。

(ii)现在看都看做点集的情况，证明合并后以平均权值作为新的权值是合理的。

## 代码：

``````#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;
}``````

=================

### locusxt

POJ - 3321 Apple Tree dfs序+线段树 简单题

Apple Tree POJ - 3321 There is an apple tree outside of kaka's house. Every autumn, a lot of apples will grow in the tree. Kaka likes apple very much, so he has been carefully n......

ProLightsfxjh
2017/10/11
0
0
Tree(树链剖分+线段树延迟标记)

Tree http://poj.org/problem?id=3237 Description You are given a tree with N nodes. The tree’s nodes are numbered 1 through N and its edges are numbered 1 through N − 1. Each ......

Fighting_sh
2018/09/25
0
0
poj 1610 Quad Trees

locusxt
2013/12/05
169
0
hduoj题目分类

hlearning
2014/02/25
0
0
LCT 12 - 02 学习记录

aziint
2017/12/03
0
0

Centos6.6 安装ffmpeg视频工具

1.安装前置工具 yum -y install gcc cc cl libmpc*//后续失败的话，自己补充自己的缺少的包 2.安装yasm 1)下载wget http://www.tortall.net/projects/yasm/releases/yasm-1.3.0.tar.gz...

5分钟前
1
0

qwfys
10分钟前
4
0

11分钟前
1
0
Java mysql连接

import java.sql.DriverManager; import java.sql.SQLException; import com.mysql.jdbc.Connection; public class T { public static void main(String[] args) throws SQLException, Insta......

11分钟前
2
0
Select 选择器 的一些官网没有的用法

12分钟前
2
0