树形DP CCPC网络赛 HDU5834 Magic boy Bi Luo with his excited tree

时间：2021-07-02 07:52:19
 // 树形DP CCPC网络赛  HDU5834 Magic boy Bi Luo with his excited tree

 // 题意：n个点的树，每个节点有权值为正，只能用一次，每条边有负权，可以走多次，问从每个点出发的最大获益

 // 思路：

 // dp[i]: 从i点出发回到i点的最大值

 // d[i][0] 从i点出发不回来的最大值

 // d[i][1] 从i点出发取最大值的下一个点

 // d[i][2] 从i点出发取次大值

 // dfs1处理出这四个

 // 然后，从1开始转移，分别DP求子节点从父亲转移过来的最大值，和从父亲出去不回来的最大值

 #include <bits/stdc++.h>

 using namespace std;

 #define LL long long

 const double inf = 123456789012345.0;

 const LL MOD =100000000LL;

 const int N =1e5+;;

 #define clc(a,b) memset(a,b,sizeof(a))

 const double eps = 1e-;

 void fre() {freopen("in.txt","r",stdin);}

 void freout() {freopen("out.txt","w",stdout);}

 inline int read() {int x=,f=;char ch=getchar();while(ch>''||ch<'') {if(ch=='-') f=-; ch=getchar();}while(ch>=''&&ch<='') {x=x*+ch-'';ch=getchar();}return x*f;}

 vector<pair<int,int> > g[N];

 int a[N],ans[N];

 int dp[N],d[N][];

 void dfs1(int u,int f){

     dp[u]=a[u];

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

        int v=g[u][i].first;

        int val=g[u][i].second;

        if(v==f) continue;

        dfs1(v,u);

        dp[u]+=max(,dp[v]-*val);

     }

     d[u][]=d[u][]=a[u];

     d[u][]=-;

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

         int v=g[u][i].first;

         int val=g[u][i].second;

         if(v==f) continue;

         int tem=dp[u]-max(,dp[v]-*val)+max(,d[v][]-val);//当前选择路径不回来的最大值

         if(tem>d[u][]){

             d[u][]=d[u][];

             d[u][]=tem;

             d[u][]=i;

         }

         else if(tem>d[u][]){

             d[u][]=tem;

         }

     }

 }

 //no从父亲不回来的最大值，yes从父亲回来的最大值

 void dfs2(int u,int f,int no,int yes){

     ans[u]=max(dp[u]+no,yes+d[u][]);

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

         int v=g[u][i].first;

         int val=g[u][i].second;

         if(v==f) continue;

         int tem1,tem2;

         if(i==d[u][]) tem1=max(,d[u][]-max(,dp[v]-*val));//从父亲出去但不是最优方案的最大值

         else tem1=max(,d[u][]-max(,dp[v]-*val));

         tem2=max(,dp[u]-max(,dp[v]-*val));//从父亲出去又回来的最大值

         tem1=max(,max(tem1+yes-val,tem2+no-val));//儿子节点从父亲转移过来的是 max（父亲儿子节点出去不回来+父亲的父亲出去回来的最大值，父亲儿子节点出去回来+父亲的父亲出去不回来的最大值）

         tem2=max(,yes+tem2-*val);

         dfs2(v,u,tem1,tem2);

     }

 }

 int main(){

     int T;

     scanf("%d",&T);

     for(int cas=;cas<=T;cas++){

         int n;

         scanf("%d",&n);

         for(int i=;i<=n;i++) g[i].clear();

         for(int i=;i<=n;i++) scanf("%d",&a[i]);

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

             int u,v,x;

             scanf("%d%d%d",&u,&v,&x);

             g[u].push_back(make_pair(v,x));

             g[v].push_back(make_pair(u,x));

         }

         dfs1(,-);

         dfs2(,-,,);

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

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

     }

     return ;

 }

相关文章