题目：点击打开链接
题解：说实话，该题的思路非常明确，先求以1为根的答案，再通过根转移求出其他答案。
dp[i][0]表示以i为根的子树走下去后再走回到i的最大值，dp[i][1]表示以i为根的子树走下去终止于某个子孙结点的最大值，DP[i]表示dp[i][1]的次大值（终止的子结点不同）。
根转移的时候需要先根减去子结点的影响，再转移到子结点：如果子结点是走下去后终止的点，那么用次大值减去影响；否则用最大值减去影响。
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <vector> using namespace std; typedef long long LL; const int M=1000000007; const int N=1e5+10; int st,ed,Q[N]; int dp[N][2]; int DP[N];//dp[i][1]的次大值，不会来的子节点与dp[i][1]不同 int f[N][2]; int n,a[N]; int re[N];//i的下去不回来的子节点 int vis[N],fa[N]; vector<int>V[N],W[N]; int main() { //freopen("1.txt","r",stdin); memset(fa,0,sizeof fa); int Case;scanf("%d",&Case); for (int C=1;C<=Case;C++){ printf("Case #%d:\n",C); scanf("%d",&n); for (int i=1;i<=n;i++)scanf("%d",&a[i]); for (int i=1;i<=n;i++)V[i].clear(),W[i].clear(); for (int i=1;i<n;i++){ int u,v,w;scanf("%d%d%d",&u,&v,&w); V[u].push_back(v);W[u].push_back(w); V[v].push_back(u);W[v].push_back(w); } for (int i=1;i<=n;i++)vis[i]=0; st=0;ed=1;Q[1]=1;vis[1]=1; while (st<ed){ st++;int u=Q[st]; for (int i=0;i<int(V[u].size());i++){ int v=V[u][i]; if (!vis[v])fa[v]=u,ed++,Q[ed]=v,vis[v]=1; } } for (int i=1;i<=n;i++)dp[i][0]=dp[i][1]=0,re[i]=0,DP[i]=0; for (int i=n;i>=1;i--){ int u=Q[i]; for (int e=0;e<int(V[u].size());e++){ int v=V[u][e]; if (fa[v]==u){ if (dp[u][1]+dp[v][0]-2*W[u][e]>dp[u][1]){ DP[u]+=dp[v][0]-2*W[u][e];//DP[u]=dp[u][1]; dp[u][1]=dp[u][1]+dp[v][0]-2*W[u][e]; } if (dp[u][0]+dp[v][1]-W[u][e]>dp[u][1]){ re[u]=v; DP[u]=dp[u][1]; dp[u][1]=dp[u][0]+dp[v][1]-W[u][e]; }else if (dp[u][0]+dp[v][1]-W[u][e]>DP[u]) DP[u]=dp[u][0]+dp[v][1]-W[u][e]; if (dp[v][0]-2*W[u][e]>0){ dp[u][0]+=max(0,dp[v][0]-2*W[u][e]); } } } DP[u]+=a[u];dp[u][1]+=a[u];dp[u][0]+=a[u]; } //for (int i=1;i<=n;i++)printf("%d %d %d\n",dp[i][0],dp[i][1],DP[i]); for (int i=1;i<=n;i++)f[i][0]=f[i][1]=0; f[1][0]=dp[1][0];f[1][1]=dp[1][1]; for (int i=1;i<=n;i++){ int u=Q[i]; for (int e=0;e<int(V[u].size());e++){ int v=V[u][e]; if (fa[v]!=u)continue; f[v][0]=dp[v][0]; f[v][1]=dp[v][1]; int tmp1=f[u][0],tmp2=f[u][1]; f[u][0]-=max(0,dp[v][0]-2*W[u][e]); if (re[u]!=v)f[u][1]-=max(0,dp[v][0]-2*W[u][e]); else if (re[u]==v)f[u][1]=DP[u]-max(0,dp[v][0]-2*W[u][e]); if (f[u][0]-2*W[u][e]>0){ DP[v]+=max(0,f[u][0]-2*W[u][e]);//DP[v]=f[v][1]; f[v][1]+=max(0,f[u][0]-2*W[u][e]); } if (f[v][0]+f[u][1]-W[u][e]>f[v][1]){ re[v]=u; DP[v]=f[v][1]; f[v][1]=f[v][0]+f[u][1]-W[u][e]; }else if (f[v][0]+f[u][1]-W[u][e]>DP[v]) DP[v]=f[v][0]+f[u][1]-W[u][e]; f[v][0]+=max(0,f[u][0]-2*W[u][e]); f[u][0]=tmp1;f[u][1]=tmp2; } } for (int i=1;i<=n;i++)printf("%d\n",f[i][1]); } return 0; } /* 2 4 4 10 6 9 1 2 7 1 3 2 2 4 3 6 8 8 7 7 10 6 1 2 3 2 3 3 3 4 1 2 5 4 5 6 8 ans: Case #1: 15 16 17 17 Case #2: 25 22 25 26 26 24 */
