codeforces1485 E. Move and Swap（dp）

E. Move and Swap

Heltion
由于紅色硬幣向下一層走的時候只能走兒子，而藍色無限制（對后續操作無影響），于是考慮下面表示

狀態表示： f u f_u fu?表示當前是紅色硬幣，向下一層走后的最大價值，
狀態轉移：
假設下一步走到兒子 v v v，并且不交換，也就是 v v v是紅色硬幣，存在轉移 f u = f v + ∣ a v ? a m ∣ f_u=f_v+|a_v-a_m| fu?=fv?+∣av??am?∣， m m m表示與 v v v同層的那些節點

如果交換，那么 v v v就是藍色硬幣，需要找到一個與 v v v同層的節點 m m m（作為紅色）存在轉移 f u = f m + ∣ a v ? a m ∣ f_u=f_m+|a_v-a_m| fu?=fm?+∣av??am?∣

去掉絕對值，預處理一些東西輔助轉移即可（ v → u v\to u v→u）我為人人轉移

#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#pragma GCC optimize(2)
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
using ll=long long;
constexpr int N=200010;
constexpr ll INF=0x3f3f3f3f3f3f3f3f;
int h[N],e[2*N],ne[2*N],idx;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
int d[N];
ll a[N];
vector<int> g[N];
ll f[N];
int fa[N],n;
void dfs_d(int u)
{
    d[u]=d[fa[u]]+1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa[u]) continue;
        fa[j]=u;
        dfs_d(j);
    }
}
void bfs(int S)
{
    for(int i=S;i>1;i--)
    {
        // 不交換顏色u由兒子v轉移
        ll vmin=INF,vmax=-INF;
        for(int v:g[i]) vmin=min(vmin,a[v]),vmax=max(vmax,a[v]);
        for(int v:g[i])
        {
            int u=fa[v];
            f[u]=max(f[u],max(a[v]-vmin,vmax-a[v])+f[v]);
        }
        // 交換顏色由同層節點轉移
        ll p1=-INF,p2=-INF;
        for(int v:g[i]) p1=max(p1,f[v]+a[v]),p2=max(p2,f[v]-a[v]);
        for(int v:g[i])
        {
            int u=fa[v];
            f[u]=max(f[u],p1-a[v]);
            f[u]=max(f[u],p2+a[v]);
        }   
    }
}
void init(int n)
{
    memset(h,-1,(n+1)*sizeof(int));idx=0;
    memset(d,0,(n+1)*sizeof(int));
    memset(fa,0,(n+1)*sizeof(int));
    memset(f,0,(n+1)*sizeof(ll));
    for(int i=0;i<=n;i++) g[i].clear();
}
int main()
{
    IO;
    int T=1;
    cin>>T;
    while(T--)
    {
        cin>>n;
        init(n);
        for(int i=2;i<=n;i++)
        {
            int v;
            cin>>v;
            add(v,i),add(i,v);
        }
        for(int i=2;i<=n;i++) cin>>a[i];
        dfs_d(1);
        for(int i=1;i<=n;i++) 
            g[d[i]].push_back(i);
        bfs(*max_element(d+1,d+1+n));
        cout<<f[1]<<'\n';
    }
    return 0;
}

寫的時候狀態定義不好，導致不容易轉移，以后狀態定義明確后在下手！