树型dp hdu5834 Magic boy Bi Luo with his excited tree

传送门：点击打开连接
题意：一棵树，对于每个点出发，结束位置可以是任意的，走过的点权值只加一次，走过的边权值要减去走过的次数乘以边权值。
问对于每一个点，权值和最大是多少。
思路：
我们需要维护4个内容
A[u]表示从u往下走，并回到u，路上的最大权值之和
B[u]表示从u往下走，不需要回到u，路上的最大权值之和
C[u]表示从u往上走，需要回到u，路上的最大权值之和
D[u]表示从u往上走，不需要回到u，路上的最大权值之和
上面这4种权值之和都不包括u本身
W[u]表示u节点的权值

f(x)=max(x,0)
若v是u的第i个节点，第一遍DFS从下往上更新,那么有
pre[i]=pre[i?1]+f(A[v]+W[v]?2?cost)
suf[i]=suf[i+1]+f(A[v]+W[v]?2?cost)
A[u]=suf[1]
B[u]=max(pre[i?1]+suf[i+1]+f(B[v]+W[v]?cost))
第二遍DFS从上往下更新，有
suf2[i]=max(suf2[i?1],f(B[v]+W[v]?cost)?f(A[v]+W[v]?2?cost))
pre2[i]=max(pre2[i?1],f(B[v]+W[v]?cost)?f(A[v]+W[v]?2?cost))
C[v]=f(pre[i?1]+suf[i+1]+C[u]+W[u]?2?cost)
D[v]=f(pre[i?1]+suf[i+1]+C[u]+W[u]+max(pre2[i?1],suf2[i+1])?cost)
D[v]=max(D[v],f(pre[i?1]+suf[i+1]+D[u]+W[u]?cost)
答案 ans[u]=max(A[u]+D[u],B[u]+C[u])+W[u]

#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);
//#pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;

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

int Head[MX],erear;
struct Edge {
    int v,cost,nxt;
} E[MX * 2];
void edge_init() {
    erear = 0;
    memset(Head,-1,sizeof(Head));
}
void edge_add(int u,int v,int cost) {
    E[erear].v = v;
    E[erear].cost = cost;
    E[erear].nxt = Head[u];
    Head[u] = erear++;
}

int ans[MX];
int W[MX],A[MX],B[MX],C[MX],D[MX];
int get_child(int u,int f,vector<int> &ch) {
    int tot = 0;
    for(int i = Head[u]; ~i; i = E[i].nxt) {
        int v = E[i].v;
        if(v == f) continue;
        tot++;
    }
    ch.resize(tot + 1); tot = 0;
    for(int i = Head[u]; ~i; i = E[i].nxt) {
        int v = E[i].v;
        if(v == f) continue;
        ch[++tot] = i;
    }
    return tot;
}
inline int func(int x) {
    return max(x,0);
}
void DFS1(int u,int f) {
    vector<int> ch,suf;
    int tot = get_child(u,f,ch);
    suf.resize(tot + 2);

    A[u] = B[u] = 0;
    suf[tot + 1] = 0;
    for(int i = tot; i >= 1; i--) {
        int v = E[ch[i]].v,cost = E[ch[i]].cost;
        DFS1(v,u);
        suf[i] = suf[i + 1] + func(A[v] + W[v] - 2 * cost);
    }
    A[u] = suf[1];

    int pre = 0;
    for(int i = 1; i <= tot; i++) {
        int v = E[ch[i]].v,cost = E[ch[i]].cost;
        B[u] = max(B[u],pre + suf[i + 1] + func(B[v] + W[v] - cost));
        pre += func(A[v] + W[v] - 2 * cost);
    }
}
void DFS2(int u,int f) {
    ans[u] = max(A[u] + D[u],B[u] + C[u]) + W[u];

    vector<int> ch,suf,suf2;
    int tot = get_child(u,ch);
    suf.resize(tot + 2);
    suf2.resize(tot + 2);

    suf[tot + 1] = suf2[tot + 1] = 0;
    for(int i = tot; i >= 1; i--) {
        int v = E[ch[i]].v,cost = E[ch[i]].cost;
        suf[i] = suf[i + 1] + func(A[v] + W[v] - 2 * cost);
        suf2[i] = max(suf2[i + 1],func(B[v] + W[v] - cost) - func(A[v] + W[v] - 2 * cost));
    }

    int pre = 0,pre2 = 0;
    for(int i = 1; i <= tot; i++) {
        int v = E[ch[i]].v,cost = E[ch[i]].cost;
        C[v] = func(pre + suf[i + 1] + C[u] + W[u] - 2 * cost);
        D[v] = func(pre + suf[i + 1] + C[u] + W[u] + max(pre2,suf2[i + 1]) - cost);
        D[v] = max(D[v],func(pre + suf[i + 1] + D[u] + W[u] - cost));
        pre += func(A[v] + W[v] - 2 * cost);
        pre2 = max(pre2,func(B[v] + W[v] - cost) - func(A[v] + W[v] - 2 * cost));
        DFS2(v,u);
    }
}

int main() {
    //FIN;
    int T,n,ansk = 0;
    scanf("%d",&T);
    while(T--) {
        printf("Case #%d:\n",++ansk);
        edge_init();
        scanf("%d",&n);
        for(int i = 1; i <= n; i++) scanf("%d",&W[i]);
        for(int i = 1; i <= n - 1; i++) {
            int u,v,cost;
            scanf("%d%d%d",&u,&v,&cost);
            edge_add(u,cost);
            edge_add(v,u,cost);
        }
        DFS1(1,-1);

        C[1] = D[1] = 0;
        DFS2(1,-1);
        for(int i = 1; i <= n; i++) {
            printf("%d\n",ans[i]);
            // printf("%d,%d,%d\n",A[i],B[i],C[i],D[i]);
        }
    }
    return 0;
}

【免责声明】本站内容转载自互联网，其相关言论仅代表作者个人观点绝非权威，不代表本站立场。如您发现内容存在版权问题，请提交相关链接至邮箱：bqsm@foxmail.com，我们将及时予以处理。