Move and Swap 树形dp

题目链接
题意：有一棵树每个点有权值，有红色点和蓝色点从1出发，每次操作远离根走一步，红色点可以选择往自己子树走一步，蓝色点可以走到他的深度+1的节点，不一定要是子树，每次操作还可以交换蓝色和红色点，每次的贡献是｜aj-ai|，问和的最大值。
思路：
dp[i]代表红色点走到i的最大答案，转移有四种，有两种是不交换，也就是dp[fa[i]]+abs(a[i]-a[j]),由于dp[fa[i]]已经知道，那么最大值无非就是这一层的最大值或者最小值。还有另外两种是交换红蓝点，那么就是max(dp[fa[j]]+a[j]-a[u],dp[fa[j]]-a[j]+a[u]),那么就要维护每一层的dp[fa[i]]+a[i]和dp[fa[i]]-a[i]的最大值。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200010;
vector<int>v[N];
int n;
int dp[N];
int d[N];
int a[N];
int dep[N][2];
int mx[N];
int ffa[N];
int mx2[N];
struct node{
    int v;
    int stp;
    int fa;
};
void dfs(int u,int fa,int d)
{
    dp[u]=max(dep[d-1][0]-a[u],dep[d-1][1]+a[u]);
    for(auto j:v[u])
    {
        if(j==fa)    continue;
        dep[d][0]=max(dep[d][0],dp[u]+a[j]);
        dep[d][1]=max(dep[d][1],dp[u]-a[j]);
    }
    for(auto j:v[u])
    {
        if(j==fa)    continue;
        dfs(j,u,d+1);
    }
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {

    cin >> n ;
    for(int i=1;i<=n;i++)
    {
        mx[i]=0;
        mx2[i]=1e18;
        v[i].clear();
        dep[i][0]=dep[i][1]=-1e18;
        dp[i]=-1e18;
        d[i]=0;
    }
    for(int i=2;i<=n;i++)
    {
        int x;
        cin>>x;
        ffa[i]=x;
        v[i].push_back(x);
        v[x].push_back(i);
    }
    a[1]=0;
    dep[0][0]=dep[0][1]=0;
    for(int i=2;i<=n;i++)
        cin>>a[i];
        dp[1]=0;
        int res=0;
        queue<node>q;
        q.push({1,1,0});
        while(q.size())
        {
            auto tt=q.front();
            q.pop();
            int u=tt.v;
            int d=tt.stp;
            int fa=tt.fa;
            dp[u]=max(max(dp[ffa[u]]+a[u]-mx2[d-1],dep[d-1][0]-a[u]),dep[d-1][1]+a[u]);
            dp[u]=max(dp[u],dp[ffa[u]]-a[u]+mx[d-1]);
            for(auto j:v[u])
            {
            if(j==fa)    continue;
            mx[d]=max(a[j],mx[d]);
            mx2[d]=min(mx2[d],a[j]);
            dep[d][0]=max(dep[d][0],dp[u]+a[j]);
            dep[d][1]=max(dep[d][1],dp[u]-a[j]);
            }
                for(auto j:v[u])
            {
                if(j==fa)    continue;
                q.push({j,d+1,u});
            }
        }
        for(int i=2;i<=n;i++)
        {
            if(v[i].size()==1)
            res=max(res,dp[i]);
        }
        cout<<res<<"\n";
    }

    return 0;
}