Magic boy Bi Luo with his excited tree

Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1058 Accepted Submission(s): 308

Problem Description

Bi Luo is a magic boy, he also has a migic tree, the tree has N nodes , in each node , there is a treasure, it's value is V[i], and for each edge, there is a cost C[i], which means every time you pass the edge i , you need to pay C[i].

You may attention that every V[i] can be taken only once, but for some C[i] , you may cost severial times.

Now, Bi Luo define ans[i] as the most value can Bi Luo gets if Bi Luo starts at node i.

Bi Luo is also an excited boy, now he wants to know every ans[i], can you help him?

Input

First line is a positive integer T(T≤104) , represents there are T test cases.

Four each test：

The first line contain an integer N(N≤105).

The next line contains N integers V[i], which means the treasure’s value of node i(1≤V[i]≤104).

For the next N−1 lines, each contains three integers u,v,c , which means node u and node v are connected by an edge, it's cost is c(1≤c≤104).

You can assume that the sum of N will not exceed 106.

Output

For the i-th test case , first output Case #i: in a single line , then output N lines , for the i-th line , output ans[i] in a single line.

Sample Input

1
5
4 1 7 7 7
1 2 6
1 3 1
2 4 8
3 5 2

Sample Output

Case #1:
15
10
14
9
15

Author

UESTC

Source

2016中国大学生程序设计竞赛 - 网络选拔赛

题意：给你一棵树,每个结点有个宝藏价值w,每次只能拿一次宝藏,每次经过路径需要花费val值,路径可以来回经过,同时可以多次花费val值,求从i点出发,能拿到的最大权值ans【i】

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <iostream>

#include <cmath>

#include <map>

#include <stack>

#include <queue>

#include <vector>

#include <bitset>

#include <set>

#define MM(a,b) memset(a,b,sizeof(a));

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

#define CT continue

#define SC scanf

const int N=1e5+10;

int val[N],dp[N][6],ans[N];

struct edge{

   int v,c;

};

vector<edge> G[N];

void dfs1(int u,int f)

{

    dp[u][1]=dp[u][0]=val[u];

    for(int i=0;i<G[u].size();i++){

        int v=G[u][i].v,c=G[u][i].c;

        if(v==f) CT;

        dfs1(v,u);

        int cur=dp[u][0]-c+dp[v][1],

            ano1=dp[u][1]+max(dp[v][0]-2*c,0),

            ano2=dp[u][2]+max(dp[v][0]-2*c,0);

        if(cur>ano1){

            dp[u][4]=v;

            dp[u][1]=cur;

            dp[u][2]=ano1;

        }

        else if(cur>ano2)  {

            dp[u][1]=ano1;

            dp[u][2]=cur;

        }

        else{

            dp[u][1]=ano1;

            dp[u][2]=ano2;

        }

        dp[u][0]+=max(0,dp[v][0]-2*c);

    }

}

void dfs2(int u,int f,int fback,int fnback)

{

    ans[u]=max(dp[u][0]+fnback,dp[u][1]+fback);

    for(int i=0;i<G[u].size();i++){

        int v=G[u][i].v,c=G[u][i].c;

        if(v==f) CT;

        int uback=fback+dp[u][0]-max(0,dp[v][0]-2*c)-2*c,unback;

        if(v==dp[u][4]){

           unback=max(dp[u][0]-max(0,dp[v][0]-2*c)+fnback,

                      fback+dp[u][2]-max(0,dp[v][0]-2*c))-c;

        }

        else{

           unback=max(fnback+dp[u][0]-max(0,dp[v][0]-2*c),

                      fback+dp[u][1]-max(0,dp[v][0]-2*c))-c;

        }

        dfs2(v,u,max(0,uback),max(0,unback));

    }

}

int main()

{

    int cas,kk=0;

    SC("%d",&cas);

    while(cas--){

        int n;SC("%d",&n);

        MM(dp,0);

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

            SC("%d",&val[i]);

            G[i].clear();

        }

        for(int i=1;i<=n-1;i++){

            int u,v,c;

            SC("%d%d%d",&u,&v,&c);

            G[u].push_back((edge){v,c});

            G[v].push_back((edge){u,c});

        }

        dfs1(1,-1);

        dfs2(1,-1,0,0);

        printf("Case #%d:\n",++kk);

        for(int i=1;i<=n;i++) printf("%d\n",ans[i]);

    }

    return 0;

}

　题解：

巴特西

hdu 5834 Magic boy Bi Luo with his excited tree 树形dp+转移

Magic boy Bi Luo with his excited tree

最新文章

热门文章