NOIP2016模拟赛三 Problem B: 神奇的树

题面

Description

有一棵神奇的树。这棵树有N个节点，在每个节点上都有宝藏，每个宝藏价值V[i]金币；对于每条边，每经过一次都要花费C[i]金币。

值得注意的是，每个宝藏只能领取一次（也可以不领）；但对于所有的边，如果要多次走这条边，将会多次产生费用。

我们定义 ans[i] 为从点 i 出发能获得的最大金币数量。

现在，请求出 ans[1], ans[2], ..., ans[N] 。

Input

第一行包含一个整数N (N≤10^5)(N≤10^5)

接下来一行将包含N个整数 V[i] ，表示每个宝藏价值的金币数 (1≤V[i]≤104)(1≤V[i]≤104) 。

接下来N-1行，每行包含三个整数u, v, c，表示u到v有一条边，每次走都要产生花费 c (1≤c≤104)(1≤c≤104) 。

Output

输出N行，第i行表示ans[i]。

Sample Input

Sample Output

HINT

对于5%的数据，N≤10N≤10

对于40%的数据，N≤1000N≤1000

对于100%的数据，N≤100000

Solution

虽然说这题的(n le 100000), 但其正解仍然是线性做法.

树上DP. 我们要计算的是每个点往下走回来 / 不回来, 往上走回来 / 不回来的最大收益. 考虑到我们可能重复计算往上走后往下走的重复走某一段的情况, 我们还需要对往下走并且不回来的情况记录最大值和次大值.

总之很麻烦就对了.

总结经验:

不要通过数据大小猜测正解的时间复杂度. 把一个方法想到底.
DP题假如实在不会的话, 果断跳过, 找思维量更小的数据结构题.

#include <cstdio>
#include <cctype>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;
namespace Zeonfai
{
    inline int getInt()
    {
        int a = 0, sgn = 1; char c;
        while(! isdigit(c = getchar())) if(c == '-') sgn *= -1;
        while(isdigit(c)) a = a * 10 + c - '0', c = getchar();
        return a * sgn;
    }
}
const int N = (int)1e5;
struct tree
{
    struct edge
    {
        int v, w;
        inline edge(int _v, int _w) {v = _v; w = _w;}
    };
    struct node
    {
        vector<edge> edg;
        int w, lst;
        int flg;
        int f; // 往下, 回
        int mx[2], g[2]; // 往下, 不回
        int upF, upG; // 往上, 回 / 不回
        inline node()
        {
            edg.clear();
            flg = 0;
            f = 0;
            mx[0] = mx[1] = -1; g[0] = g[1] = 0;
            upF = upG = 0;
        }
    }nd[N + 1];
    inline void addEdge(int u, int v, int w)
    {
        nd[u].edg.push_back(edge(v, w)); nd[v].edg.push_back(edge(u, w));
    }
    void down(const int u, const int pre, int w)
    {
        nd[u].lst = w;
        nd[u].f = nd[u].w;
        for(auto edg : nd[u].edg) if(edg.v != pre)
        {
            down(edg.v, u, edg.w);
            if(nd[edg.v].f > edg.w * 2) nd[edg.v].flg = 1, nd[u].f += nd[edg.v].f - edg.w * 2;
        }
        nd[u].g[0] = nd[u].g[1] = nd[u].f;
        for(auto edg : nd[u].edg) if(edg.v != pre)
        {
            int v = edg.v;
            for(int i = 0; i < 2; ++ i)
                if(nd[u].mx[i] == -1
                   && nd[v].g[0] - nd[v].lst - nd[v].flg * (nd[v].f - nd[v].lst * 2) > 0
                   || nd[u].mx[i] != -1
                   && nd[v].g[0] - nd[v].lst - nd[v].flg * (nd[v].f - nd[v].lst * 2)
                   > nd[nd[u].mx[i]].g[0] - nd[nd[u].mx[i]].lst - nd[nd[u].mx[i]].flg * (nd[nd[u].mx[i]].f - nd[nd[u].mx[i]].lst * 2))
                {
                    if(i == 0) nd[u].mx[1] = nd[u].mx[0];
                    nd[u].mx[i] = v;
                    break;
                }
        }
        for(int i = 0; i < 2; ++ i) if(~ nd[u].mx[i])
            nd[u].g[i] = nd[u].f
                         + nd[nd[u].mx[i]].g[0] - nd[nd[u].mx[i]].lst
                         - nd[nd[u].mx[i]].flg * (nd[nd[u].mx[i]].f - nd[nd[u].mx[i]].lst * 2);
    }
    void up(const int u, const int pre)
    {
        if(~ pre)
        {
            nd[u].upF = nd[pre].upF + nd[pre].f - (nd[u].f - nd[u].lst * 2) * nd[u].flg - nd[u].lst * 2;
            nd[u].upF = max(0, nd[u].upF);
            int tmp;
            if(u == nd[pre].mx[0]) tmp = nd[pre].g[1] - (nd[u].f - nd[u].lst * 2) * nd[u].flg;
            else tmp = nd[pre].g[0] - (nd[u].f - nd[u].lst * 2) * nd[u].flg;
            nd[u].upG = max(tmp + nd[pre].upF, nd[pre].f - (nd[u].f - nd[u].lst * 2) * nd[u].flg + nd[pre].upG) - nd[u].lst;
            nd[u].upG = max(0, nd[u].upG);
        }
        for(auto edg : nd[u].edg) if(edg.v != pre) up(edg.v, u);
    }
}T;
int main()
{

#ifndef ONLINE_JUDGE

    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);

#endif

    using namespace Zeonfai;
    int n = getInt();
    for(int i = 1; i <= n; ++ i) T.nd[i].w = getInt();
    for(int i = 1; i < n; ++ i)
    {
        int u = getInt(), v = getInt(), w = getInt();
        T.addEdge(u, v, w);
    }
    T.down(1, -1, 0);
    T.up(1, -1);
    for(int i = 1; i <= n; ++ i)
        // printf("%d %d ", T.nd[i].f + T.nd[i].upG, T.nd[i].upF + T.nd[i].g[0]);
        printf("%d
", max(T.nd[i].f + T.nd[i].upG, T.nd[i].upF + T.nd[i].g[0]));
        // printf("%d %d %d %d
", T.nd[i].f, T.nd[i].upG, T.nd[i].upF, T.nd[i].g[0]);
}