HDU 5834 Magic boy Bi Luo with his excited tree（树形dp）

题意是给你一个树，让你求出以任意一个点为起点，走到的最大权值和，走过一个点，权值只能获得一次，每走过一条边，就要花费cost
这题需要维护4个数组，dfs两次
A数组表示从i往下走，回到i的最大权值和
B数组表示从i往下走，不回到i的最大权值和
C数组表示从i往上走，回到i的最大权值和
D数组表示从i往上走，不回到i的最大权值和
第一次dfs，维护A,B数组
开两个数组pre和suf，存节点u的子节点，一个从前往后一个从后往前
pre[i]=pre[i?1]+max(A[v]+w[v]?2?cost,0)
suf[i]=suf[i+1]+max(A[v]+w[v]?2?cost)
A[u]=suf[1]
B[u]=max(pre[i?1]+suf[i+1]+max(B[v]+w[v]?cost,0))
第二次dfs，维护C,D数组
首先一样维护出来pre和suf数组
然后开个pre2和suf2数组，表示前缀和后缀里面，把一个节点往下走回来改成不回来
pre2[i]=max(pre2[i?1],max(B[v]+w[v]?cost,0)?max(A[v]+w[v]?2?cost,0))
suf2[i]=max(suf2[i+1],max(B[v]+w[v]?cost,0)?max(A[v]+w[v]?2?cost,0))
C[v]=max(0,C[u]+w[u]+pre[i?1]+suf[i+1]?2?cost)
D[v]=max(C[u]+w[u]?cost+pre[i?1]+suf[i+1]+max(pre2[i?1],suf2[i+1]),D[u]+w[u]?cost+pre[i?1]+suf[i+1])

代码：

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#pragma comment(linker,"/STACK:102400000,102400000")

using namespace std;
#define MAX 100005
#define MAXN 1000005
#define maxnode 205
#define sigma_size 26
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lrt rt<<1
#define rrt rt<<1|1
#define middle int m=(r+l)>>1
#define LL long long
#define ull unsigned long long
#define mem(x,v) memset(x,v,sizeof(x))
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define bits(a) __builtin_popcount(a)
#define mk make_pair
#define limit 10000

//const int prime = 999983;
const int    INF   = 0x3f3f3f3f;
const LL     INFF  = 0x3f3f;
const double pi    = acos(-1.0);
const double inf   = 1e18;
const double eps   = 1e-4;
const LL    mod    = 772002;
const ull    mx    = 133333331;

/*****************************************************/
inline void RI(int &x) {
      char c;
      while((c=getchar())<'0' || c>'9');
      x=c-'0';
      while((c=getchar())>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0';
 }
/*****************************************************/

int w[MAX];
struct Edge{
    int v,next,c;
}edge[MAX*2];
int head[MAX];
int tot;
int A[MAX];
int B[MAX];
int C[MAX];
int D[MAX];
int pre[MAX];
int pre2[MAX];
int suf[MAX];
int suf2[MAX];
int ans[MAX];
vector<pii> ch;

void add_edge(int a,int b,int c){
    edge[tot]=(Edge){b,head[a],c};
    head[a]=tot++;
}

void dfs1(int u,int fa){
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa) continue;
        dfs1(v,u);
    }
    ch.clear();
    ch.push_back(mk(0,0));
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa) continue;
        ch.push_back(mk(v,edge[i].c));
    }
    pre[0]=suf[ch.size()]=0;
    for(int i=1;i<ch.size();i++){
        pre[i]=pre[i-1]+max(A[ch[i].first]+w[ch[i].first]-2*ch[i].second,0);
    }
    for(int i=ch.size()-1;i>0;i--){
        suf[i]=suf[i+1]+max(A[ch[i].first]+w[ch[i].first]-2*ch[i].second,0);
    }
    A[u]=suf[1];
    for(int i=1;i<ch.size();i++){
        B[u]=max(B[u],suf[i+1]+pre[i-1]+max(w[ch[i].first]+B[ch[i].first]-ch[i].second,0));
    }
}

void dfs2(int u,int fa){
    ch.clear();
    ch.push_back(mk(0,0));
    ans[u]=max(A[u]+D[u],B[u]+C[u])+w[u];
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa) continue;
        ch.push_back(mk(v,edge[i].c));
    }
    pre[0]=pre2[0]=0;
    for(int i=1;i<ch.size();i++){
        pre[i]=pre[i-1]+max(A[ch[i].first]+w[ch[i].first]-2*ch[i].second,0);
        pre2[i]=max(pre2[i-1],max(B[ch[i].first]+w[ch[i].first]-ch[i].second,0)-max(A[ch[i].first]+w[ch[i].first]-2*ch[i].second,0));
    }
    suf[ch.size()]=suf2[ch.size()]=0;
    for(int i=ch.size()-1;i>0;i--){
        suf[i]=suf[i+1]+max(A[ch[i].first]+w[ch[i].first]-2*ch[i].second,0);
        suf2[i]=max(suf2[i+1],0));
    }
    for(int i=1;i<ch.size();i++){
        C[ch[i].first]=max(pre[i-1]+suf[i+1]+C[u]+w[u]-2*ch[i].second,0);
        D[ch[i].first]=max(0,max(D[u]+w[u]-ch[i].second+pre[i-1]+suf[i+1],C[u]+w[u]-ch[i].second+pre[i-1]+suf[i+1]+max(pre2[i-1],suf2[i+1])));
    }
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa) continue;
        dfs2(v,u);
    }
}
int main(){
    //freopen("froggy.in","r",stdin);
    //freopen("froggy.out","w",stdout);
    int t,kase=0;
    cin>>t;
    while(t--){
        int n;
        scanf("%d",&n);
        tot=0;
        for(int i=1;i<=n;i++){
            head[i]=-1;
            A[i]=B[i]=C[i]=D[i]=0;
        }
        for(int i=1;i<=n;i++) scanf("%d",&w[i]);
        for(int i=1;i<n;i++){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            add_edge(a,c);
            add_edge(b,a,c);
        }
        dfs1(1,-1);
        dfs2(1,-1);
        kase++;
        printf("Case #%d:n",kase);
        for(int i=1;i<=n;i++) printf("%dn",ans[i]);
    }
    return 0;
}

（编辑：威海站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!