[Poi2014]FarmCraft

发表于 | 分类于

题目

mhy住在一棵有n个点的树的1号结点上，每个结点上都有一个妹子。

mhy从自己家出发，去给每一个妹子都送一台电脑，每个妹子拿到电脑后就会开始安装zhx牌杀毒软件，第i个妹子安装时间为Ci。
树上的每条边mhy能且仅能走两次，每次耗费1单位时间。mhy送完所有电脑后会回自己家里然后开始装zhx牌杀毒软件。
卸货和装电脑是不需要时间的。
求所有妹子和mhy都装好zhx牌杀毒软件的最短时间。

INPUT

第一行输入一个整数N，表示有N个结点
第二行有N个整数C1,C2…Cn，Ci表示第i个妹子安装杀毒软件的时间
接下来的N-1行，每行两个整数x，y，表示x与y之间有一条无向边

OUTPUT

输出文件仅包含一行，一个整数表示让所有妹子和mhy装好杀毒软件的最短时间

SAMPLE

INPUT

6
1 8 9 6 3 2
1 3
2 3
3 4
4 5
4 6

OUTPUT

11

解题报告

翻译真累= =，原题英文版，结果发现翻译跟英文啥关系没有，就粘了翻译，然后发现输入格式跟输出格式都没有翻译，然后= =，然后我就强行翻译了一发= =
考试时打了个dfs，骗了5分- -
正解：
贪心。
我们分析题干，发现每条边只能过两次，也就是一进一出，那么我们进了一个点，我们就要遍历完整个子树，所以我们只能跑一遍dfs，然后我们发现dfs一遍的时间是一定的，那么见每个妹子的时间就在这个时间轴上。
我们定义一个数组rest，代表遍历完这个节店的子树，以后我们还要为这个节点所费的时间。

  1. 除了1节点，见到一个妹子杀一下毒
  2. 我们发现答案是Max(rest[1],c[1])+2×(n-1)
  3. 我们考虑如何找rest，我们发现，每个节点的最优rest是 子节点的rest，减去其在这个子树里又经过的时间 再和 它的c减去遍历它的时间 取个Max 
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
inline int read(){
    int sum(0);
    char ch(getchar());
    for(;ch<'0'||ch>'9';ch=getchar());
    for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
    return sum;
}
int n;
int w[500001];
int fa[500001],t[500001],rest[500001];
inline int my_max(int a,int b){
    return a>b?a:b;
}
inline int my_min(int a,int b){
    return a<b?a:b;
}
vector<int>g[500001];
inline bool cmp(const int &a,const int &b){
    return rest[a]>rest[b];
}
inline void dfs(int u){
    int size(g[u].size());
    for(int i=0;i<size;i++){
        int e(g[u][i]);
        if(e!=fa[u]){
            t[u]++;
            fa[e]=u;
            dfs(e);
            t[u]++;
            t[u]+=t[e];
        }
    }
    if(u!=1)
        rest[u]=w[u]-t[u];
    int tmp(t[u]);
    sort(g[u].begin(),g[u].end(),cmp);
    for(int i=0;i<size;i++){
        int e(g[u][i]);
        if(e!=fa[u]){
            tmp-=2+t[e];
            rest[u]=my_max(rest[u],rest[e]-tmp-1);
        }
    }
    rest[u]=my_max(0,rest[u]);
//  cout<<u<<' '<<w[u]<<' '<<rest[u]<<endl;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)
        w[i]=read();
    for(int i=1;i<n;i++){
        int x(read()),y(read());
        g[x].push_back(y),g[y].push_back(x);
    }
    dfs(1);
    printf("%d",my_max(rest[1],w[1])+(n<<1)-2);
}