题解P3574 [POI2014]FAR-FarmCraft

P3574 [POI2014]FAR-FarmCraft

贪心+DP

随便猜了一个贪心策略居然就A了,那我就来简单证明一下这个贪心策略

令 $f_i$ 表示以 $i$ 为根的子树内,从 $i$ 出发开始安装电脑所需的最长时间, $t_i$ 表示遍历完整棵子树所需的时间

按照 $f_i-t_i$ 从大到小排序然后转移,答案即为最优的

证明

对于当前子树 $u$, 以及它的三个儿子 $v_1,v_2$

假设 $f_{v_1}-t_{v_1} > f_{v_2}-t_{v_2} \Rightarrow f_{v_1}+t_{v_2}>f_{v_2}+t{v_1}$,遍历完之前的儿子结点所用的时间为 $sum$

若先遍历 $v_1$,那么两次遍历的答案为 $sum+f_{v_1},sum+t_1+f_{v_2}$

若先遍历 $v_2$,那么两次遍历的答案为 $sum+f_{v_2},sum+t_2+f_{v_1}$

那么哪一个更优呢?显然 $sum+t_2+f_{v_1}>sum+t_1+f_{v_2}>sum+f_{v_1}$

即先遍历 $v_1$ 会更优

证毕

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 5e5 + 5;

int c[N], sum[N];
int head[2 * N], ver[2 * N], net[2 * N], idx;
struct typ
{
    int t, maxn;
    bool operator < (const typ a) const
    {
        return maxn - t < a.maxn - a.t;
    }
} f[N];

void add(int a, int b)
{
    net[++idx] = head[a], ver[idx] = b, head[a] = idx;
}

void dfs(int u, int fa, int dis)
{
    priority_queue<typ> q;
    f[u].maxn = c[u];
    for (int i = head[u]; i; i = net[i])
    {
        int v = ver[i];
        if (v == fa)
            continue;
        dfs(v, u, dis + 1);
        q.push(f[v]);
    }
    while (!q.empty())
    {
        int t = q.top().t, maxn = q.top().maxn;
        q.pop();
        f[u].maxn = max(f[u].maxn, f[u].t + maxn + 1);
        f[u].t += t + 2;
    }
}   

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    for (int i = 1; i < n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }
    dfs(1, 0, 0);
    printf("%d", max(f[1].maxn, 2 * n - 2 + c[1]));
    return 0;
}