BZOJ 3829 FarmCraft

Posted on | | 阅读数 次
Words count in article: 1.2k | Reading time ≈ 6

题目描述

In a village called Byteville, there are houses connected with N-1 roads. For each pair of houses, there is a unique way to get from one to another. The houses are numbered from 1 to . The house no. 1 belongs to the village administrator Byteasar. As part of enabling modern technologies for rural areas framework, computers have been delivered to Byteasar’s house. Every house is to be supplied with a computer, and it is Byteasar’s task to distribute them. The citizens of Byteville have already agreed to play the most recent version of FarmCraft (the game) as soon as they have their computers.

Byteasar has loaded all the computers on his pickup truck and is about to set out to deliver the goods. He has just the right amount of gasoline to drive each road twice. In each house, Byteasar leaves one computer, and immediately continues on his route. In each house, as soon as house dwellers get their computer, they turn it on and install FarmCraft. The time it takes to install and set up the game very much depends on one’s tech savviness, which is fortunately known for each household. After he delivers all the computers, Byteasar will come back to his house and install the game on his computer. The travel time along each road linking two houses is exactly 1 minute, and (due to citizens’ eagerness to play) the time to unload a computer is negligible.

Help Byteasar in determining a delivery order that allows all Byteville’s citizens (including Byteasar) to start playing together as soon as possible. In other words, find an order that minimizes the time when everyone has FarmCraft installed.

输入

The first line of the standard input contains a single integer N(2<=N<=5 00 000) that gives the number of houses in Byteville. The second line contains N integers C1,C2…Cn(1<=Ci<=10^9), separated by single spaces; Ci is the installation time (in minutes) for the dwellers of house no. i.

The next N-1 lines specify the roads linking the houses. Each such line contains two positive integers a and b(1<=a<b<=N) , separated by a single space. These indicate that there is a direct road between the houses no. a and b.

输出

The first and only line of the standard output should contain a single integer: the (minimum) number of minutes after which all citizens will be able to play FarmCraft together.

样例输入

6

1 8 9 6 3 2

1 3

2 3

3 4

4 5

4 6

样例输出

11

Hits

Explanation: Byteasar should deliver the computers to the houses in the following order: 3, 2, 4, 5, 6, and 1. The game will be installed after 11, 10, 10, 10, 8, and 9 minutes respectively, in the house number order. Thus everyone can play after 11 minutes.

If Byteasar delivered the game in the following order: 3, 4, 5, 6, 2, and 1, then the game would be installed after: 11, 16, 10, 8, 6, and 7 minutes respectively. Hence, everyone could play only after 16 minutes.

题意

zuhiul是镇长，住在1号房子，镇里的房子构成了一颗树，现在zuhiul要给镇里其他房子里的小姐姐送电脑，每经过一条路径，zuhiul都要花掉一分钟(才不是为了看小姐姐)。但是zuhiul只负责送不负责装，每个小姐姐的脑子都比较奇怪，有些装的快，有些装的慢，最后zuhiul会返回自己的家给自己装电脑，然后他就可以和小姐姐视频了，但是必须要等所有的小姐姐都装好了才行，现在问你zuhiul最早什么时候可以和所有的小姐姐视频。

分析

显然是树上DP，我们考虑定义DP状态，则有

f[i]表示以 i 为根的子树里，花费总时间的最大值是多少

我们定义son_num表示这个节点对应子树的节点数量

然后我们考虑转移，我们首先考虑怎么搞两个子节点的时候，然后进行推广。

不妨假设这两个字节点分别是a和b，然后可以得到先遍历a再遍历b的最大时长为

max(f[a]+1,f[b]+son_num[a]*2+1)

同理，先遍历b的最大时常为max(f[b]+1,f[a]+son_num[b]*2+1)

所以如果有max(f[a]+1,f[b]+son_num[a]2+1)<max(f[b]+1,f[a]+son_num[b]2+1)

因为f[a]+son_num[b]2+1>f[a]+1并且f[b]+son_num[a]2+1>f[b]+1

所以只需要得到 f[b]+son_num[a]2<f[a]+son_num[b]2

也即 f[b]-son_num[b]2<f[a]-son_num[a]2

同样，对于多个节点来说，我们同样只要对每个子节点按照 f[son]-son_num[son]*2降序排序，然后从前往后贪心选就行了。

代码

给大佬递上我奇丑无比的代码　(/ω＼)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>
using namespace std;
const int maxm = 7e5+10;
struct p{
    long long t,son_num;
} peo[maxm];
long long len;
vector<int>mat[maxm];
long long f[maxm];
int ind[maxm];
bool cmp(int a,int b){
    return f[a]-peo[a].son_num*2>f[b]-peo[b].son_num*2;
}
void dfs(int a,int pre){
    peo[a].son_num = 1;
    if(a!=1) f[a] = peo[a].t;
    for(int i:mat[a]){
        if(i==pre) continue;
        dfs(i,a);
    }
    ind[0] = 0;
    for(int i:mat[a]){
        if(i==pre) continue;
        ind[++ind[0]] = i;
        peo[a].son_num+=peo[i].son_num;
    }
    sort(ind+1,ind+ind[0]+1,cmp);
    long long now = 0;
    for(int i = 1;i&lt;=ind[0];i++){
        f[a] = max(f[a],f[ind[i]]+now+1);
        now+=peo[ind[i]].son_num*2;
    }
}
void solve(){
    printf("%lld\n",max(f[1],len*2-2+peo[1].t));
}
int main(){
    scanf("%lld",&len);
    for(int i = 1;i&lt;=len;i++) scanf("%lld",&peo[i].t);
    for(int i = 1,a,b;i&lt;len;i++) {
        scanf("%d%d",&a,&b);
        mat[a].push_back(b);
        mat[b].push_back(a);
    }
    dfs(1,0);
    solve();
    return 0;
}