树型dp Codeforces633F The Chocolate Spree

传送门：点击打开链接

题意：给你一棵树，有点权，求两条不相交的路径的点权和的最大值

思路：Tourist太神辣，这个代码看他的才学会的，但是他只用了10分钟敲了140行..Orz

先一次DFS求出，对于所有的点u，经过这个u点到叶子的路径点权和最大值记为down[u]，以及u的子树中一条路径点权和最大值记为best[u]

然后用队列来处理，其实也可以用DFS来处理，那么数组就不能用全局变量了，必须要用vector开在函数内部

对于每个点，把它的子节点的best记录前缀最大和后缀中最大的，down记录前缀最大和次大，后缀最大和次大。

那么就可以开始讨论了，开始枚举第i个儿子，那么我认为第1条链是在第i个儿子的子树中，那么第二条链就不能在第1条链的子树中了，只能是在i节点的左边，或者i节点的右边，或者左边和右边的结合等等，具体可以看代码。

最难想到的就是用前缀和后缀在树上经行处理，写了这道题目后有了这个思想，以后就有助于扩展思路了~

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<bitset>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define fuck(x) cout<<"["<<x<<"]"
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)
using namespace std;
typedef long long LL;

const int MX = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;

LL ans;
int n, ch[MX];
LL A[MX], best[MX], down[MX];
LL pd[MX], pd2[MX], sd[MX], sd2[MX], pb[MX], sb[MX];
int Head[MX], erear;
struct Edge {
    int v, nxt;
} E[MX * 2];
struct Data {
    int u, f; LL up;
    Data() {}
    Data(int _u, int _f, LL _up) {
        u = _u; f = _f; up = _up;
    }
};

void edge_init() {
    erear = 0;
    memset(Head, -1, sizeof(Head));
}
void edge_add(int u, int v) {
    E[erear].v = v;
    E[erear].nxt = Head[u];
    Head[u] = erear++;
}
void DFS(int u, int f) {
    LL Max = 0, Max2 = 0;
    for(int i = Head[u]; ~i; i = E[i].nxt) {
        int v = E[i].v;
        if(v == f) continue;
        DFS(v, u);
        if(down[v] > Max) {
            Max2 = Max;
            Max = down[v];
        } else if(down[v] > Max2) {
            Max2 = down[v];
        }
        best[u] = max(best[u], best[v]);
    }
    down[u] = Max + A[u];
    best[u] = max(best[u], Max + Max2 + A[u]);
}
void solve() {
    queue<Data>Q;
    Q.push(Data(1, -1, 0));
    while(!Q.empty()) {
        Data top = Q.front();
        Q.pop();

        LL up = top.up;
        int u = top.u, f = top.f, sz = 0;

        for(int i = Head[u]; ~i; i = E[i].nxt) {
            int v = E[i].v;
            if(v == f) continue;
            ch[++sz] = v;
        }
        pb[0] = pd[0] = pd2[0] = 0;
        for(int i = 1; i <= sz; i++) {
            pd[i] = pd[i - 1];
            pd2[i] = pd2[i - 1];
            int v = ch[i];

            pb[i] = max(pb[i - 1], best[v]);
            if(down[v] > pd[i]) {
                pd2[i] = pd[i];
                pd[i] = down[v];
            } else if(down[v] > pd2[i]) {
                pd2[i] = down[v];
            }
        }
        sb[sz + 1] = sd[sz + 1] = sd2[sz + 1] = 0;
        for(int i = sz; i >= 1; i--) {
            sd[i] = sd[i + 1];
            sd2[i] = sd2[i + 1];
            int v = ch[i];

            sb[i] = max(sb[i + 1], best[v]);
            if(down[v] > sd[i]) {
                sd2[i] = sd[i];
                sd[i] = down[v];
            } else if(down[v] > sd2[i]) {
                sd2[i] = down[v];
            }
        }
        for(int i = 1; i <= sz; i++) {
            int v = ch[i];
            LL now = A[u] + up + max(pd[i - 1], sd[i + 1]);
            now = max(now, max(pb[i - 1], sb[i + 1]));
            now = max(now, A[u] + pd[i - 1] + pd2[i - 1]);
            now = max(now, A[u] + sd[i + 1] + sd2[i + 1]);
            now = max(now, A[u] + pd[i - 1] + sd[i + 1]);
            now += best[v];
            ans = max(ans, now);
        }
        for(int i = 1; i <= sz; i++) {
            int v = ch[i];
            LL nup = max(up, max(pd[i - 1], sd[i + 1])) + A[u];
            Q.push(Data(v, u, nup));
        }
    }
}

int main() {
    edge_init(); //FIN;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%I64d", &A[i]);
    }
    for(int i = 1; i <= n - 1; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        edge_add(u, v);
        edge_add(v, u);
    }
    DFS(1, -1);
    solve();
    printf("%I64d\n", ans);
    return 0;
}