2016CCPC网络选拔赛C-换根dp好题

题目大意：

给一颗树，带点权和边权.问你每个点,得到的最大价值.(点权代表价值边权代表花费).每个点只能拿一次，边反复计算花费.

题目思路:

容易想出一种树形dp后换根的思路:
$dp(i,0/1)$代表以$i$为根的子树，最后回到/不回到i点的最大价值.

$dp(i,1)={\sum }_{j\in So{n}_i}max(dp(j,1)-2\ast w_i,0)$
$dp(i,0)=dp(i,1)-ma{x}_{j\in So{n}_i}(max(dp(j,0)-w_i,0)-max(dp(j,1)-2\ast w_i,0))$
下面令$g{x}_1=max(dp(j,1)-2\ast w_i,0),g{x}_2=max(dp(j,0)-w_i,0)$

再维护$se(i,0)=dp(i,1)-2_{j\in So{n}_i}^{th}(max(dp(j,0)-w_i,0)-max(dp(j,1)-2\ast w_i,0))$
和$to(i)$
（后面再讲这俩干嘛的）

转移完，考虑第二遍dfs,将父亲当作子树，把它的影响考虑进来

令新一轮的dp为$ndp,sse,tto$

注意转移的时候要将父亲dp中对于该点的贡献取消,这个部分是最复杂的:

1.当更新$ndp(i,1)$时,
父亲$fa$对点$i$的贡献$g{x}_3=max(ndp(fa,1)-g{x}_1-w_i,0)$
那么$ndp(i,1)=dp(i,1)+g{x}_3$
$ndp(i,0)=dp(i,0)+g{x}_3$ (先假设最后不留在父节点)
$sse(i)=se(i)+g{x}_3$

2.当更新$ndp(i,0)$时(most hard)

这个时候父亲节点对$i$的贡献就很复杂了，分两种情况:

2.1当$dp(fa,0)$最后不是落在子树$i$时,父亲$fa$对点$i$的贡献$g{x}_4=max(ndp(fa,1)-g{x}_1-w_i,0)$

2.2 否则,我们需要重新规划$dp(fa,0)$，让他最后的终点不要落在$i$中。那么就落在哪？
次优解！
所以此时我们需要多维护 次优值$se(i)$和 最优值落在的儿子节点$to(i)$ 用于判断是否落在子树.
那么贡献$g{x}_5=max(sse(fa,1)-g{x}_1-w_i,0)$

这时令$tmp=dp(i,1)+g{x}_4/g{x}_5-w$

用$tmp$来更新当前节点的最后留向

1.若$tmp\ge ndp(i,0)$ 代表往父亲节点走并留在那比（假设不往父亲节点走）更优，我们需要重新规划该点的$sse,tto$
$sse(i)=ndp(i,0),tto=fa$
2.否则无法更新.

PS:很久没写这么复杂的题目了。。不过还是独立完成了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define vll vector<ll>
#define fi first
#define se second
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int dp[maxn][2] , se[maxn] , f[maxn][2] , to[maxn] , a[maxn];
int tto[maxn] , sse[maxn];
vector<pii> e[maxn];
void dfs (int u , int fa){
    
    dp[u][0] = dp[u][1] = 0;
    for (auto &g : e[u]){
    
        int v = g.first , w = g.second;
        if (v == fa) continue;
        dfs(v , u);
        dp[u][1] += max(dp[v][1] - 2 * w , 0);
    }
    vector<pii> res;
    for (auto &g : e[u]){
    
        int v = g.first , w = g.second;
        if (v == fa) continue;
        int tmp = max(max(dp[v][0] - w , 0) - max(dp[v][1] - 2 * w , 0) , 0);
        res.push_back({
    tmp , v});
    }
    sort(res.begin() , res.end());
    reverse(res.begin() , res.end());
    if (res.size() > 0){
    
        dp[u][0] = dp[u][1] + res[0].first;
        to[u] = res[0].second;
        if (res.size() == 1) se[u] = 0;
        else se[u] = dp[u][1] + res[1].first;
    }else {
    
        se[u] = 0;
    }
    dp[u][0] += a[u];
    dp[u][1] += a[u];
    se[u] += a[u];
    return ;
}
void dfs1 (int u , int fa , int ww){
    
    f[u][0] = dp[u][0];
    f[u][1] = dp[u][1];
    tto[u] = to[u];
    sse[u] = se[u] + max(w , 0);
    int gx = max(0 , dp[u][1] - 2 * ww);
    int w = f[fa][1] - gx - 2 * ww; // 选择fa并回来所带来的价值w
    f[u][1] = dp[u][1] + max(w , 0);
    f[u][0] = dp[u][0] + max(w , 0);
    // 选择fa并不回来的价值ggg
    int ggg;
    if (tto[fa] == u) ggg = sse[fa] - gx - ww;
    else ggg = f[fa][0] - gx - ww;
    int ttt = dp[u][1] + max(ggg , 0);
    // f[u][0] ttt
    if (ttt >= f[u][0]){
    
        sse[u] = f[u][0];
        f[u][0] = ttt;
        tto[u] = fa;
    }else if (ttt >= sse[u]){
    
        sse[u] = ttt;
    }
    for (auto &g : e[u]){
    
        int v = g.first , w = g.second;
        if (v == fa) continue;
        dfs1(v , u , w);
    }
    return ;
}
int main()
{
    
    ios::sync_with_stdio(false);
    int t; cin >> t;
    int cnt = 0;
    while (t--){
    
        int n; cin >> n;
        for (int i = 1 ; i <= n ; i++){
    
            e[i].clear();
            tto[i] = sse[i] = dp[i][0] = dp[i][1] = se[i] = f[i][0] = f[i][1] = to[i] = 0;

        }
        for (int i = 1 ; i <= n ; i++) cin >> a[i];
        for (int i = 1 ; i < n ; i++){
    
            int x , y , z; cin >> x >> y >> z;
            e[x].pb({
    y , z});
            e[y].pb({
    x , z});
        }
        dfs (1 , 0);
        dfs1(1 , 0 , 0);
        cout << "Case #" << (++cnt) << ":" << endl;
        for (int i = 1 ; i <= n ; i++){
    
            cout << max(f[i][0] , f[i][1]) << endl;
        }
    }
    return 0;
}