【题解】POI2014FAR-FarmCraft

　　这题首先手玩一下一下数据，写出每个节点修建软件所需要的时间和到达它的时间戳（第一次到达它的时间），不难发现实际上就是要最小化这两者之和。然后就想到：一棵子树内，时间戳必然是连续的一段区间，而如果将访问到子树根节点的时间看做0时，则是一段0~x的连续时间，与其他子树的分配无关。所以自然的联想到单独处理出dp[u]：以u为根节点，访问时间看做0的时候其中节点所需要的时间最大值。

　　如何从dp[v]转移到dp[u]？首先随便给它们分配一个顺序，则每一个节点的最后最大值（原先的值建立在访问根节点的时间为0的基础上，但现在的根节点变成了原来根节点的父亲）=原来的dp值+分配的顺序所带来的时间差。我们分析应怎样分配这个顺序使得它们的最大值最小。

　　我们有

　　　　　　　　dp[u] = max{ dp[a] , dp[b] + size[a] + 2 };
　　　　　　　　dp[u] = max{ dp[u] , max{ dp[b], dp[a] + size[b] + 2 }}; // size[x] 代表访问x子树的全部节点所需要的时间

　　这个应该不难看出：实际上就是枚举了两种情况。那么如果第一次取得的值要小于第二次取得的值，我们就认为将第一个放在第二个前面是更优的。之所以+2，是因为由u->v的边还需要经过2次。

// luogu-judger-enable-o2

#include <bits/stdc++.h>

using namespace std;

#define maxn 600000

#define int long long

int n, a[maxn], size[maxn];

int cnp = , dp[maxn], head[maxn];

int read()

{

    int x = ;

    char c;

    c = getchar();

    while(c < '' || c > '') c = getchar();

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x;

}

struct node

{

    int id, num, s;

}P[maxn];

struct edge

{

    int to, last;

}E[maxn * ];

bool cmp (node a, node b)

{

    int p = max(a.num, b.num + a.s + );

    int q = max(b.num, a.num + b.s + );

    return p < q;

}

void add(int u, int v)

{

    E[cnp].to = v, E[cnp].last = head[u]; head[u] = cnp ++;

}

void DP(int u, int fa)

{

    if(u != ) dp[u] = a[u];

    for(int i = head[u]; i; i = E[i].last)

    {

        int v = E[i].to;

        if(v == fa) continue;

        DP(v, u);

    }

    int tot = , last = ;

    for(int i = head[u]; i; i = E[i].last)

        if(E[i].to != fa) P[++ tot] = (node) {E[i].to, dp[E[i].to], size[E[i].to]};

    if(tot)

    {

        sort(P + , P +  + tot, cmp);

        for(int i = ; i <= tot; i ++)

        {

            int v = P[i].id;

            dp[u] = max(dp[u], dp[v] + (size[u] + ));

            size[u] += size[v] + ;

        }

    }

}

signed main()

{

    n = read();

    for(int i = ; i <= n; i ++) a[i] = read();

    for(int i = ; i < n; i ++)

    {

        int x = read(), y = read();

        add(x, y), add(y, x);

    }

    DP(, );

    printf("%lld\n", max(dp[], (n - ) *  + a[]));

    return ;

}

巴特西

【题解】POI2014FAR-FarmCraft

最新文章

热门文章