牛客挑战赛71 B树上博弈

Link

一道很有意思的min-max博弈

用树上dp来解决，那么显然的，当前节点是谁取的会影响答案，\(dp2_{i,j}\)表示取当前阶段，被Alice/Bob取走的结果，
并且这个题是取子树上任意的节点，那么还需要保存子树上的信息，故使用\(dp_{i,j}\)记录下子树中的Alice/Bob取走的结果，然后就可以顺着dp解决这个问题了。

#include<iostream>
#include<cstdio>
using namespace std;
int ans[200005];
int t;
long long c[200005];
int head[200005];
struct ed{
    int to;
    int ne;
}edge[200005];
int p;
void add(int f,int to){
    edge[++p].to=to;
    edge[p].ne=head[f];
    head[f]=p;
    return ;
}
int f;
long long dp[200001][2];
long long dp2[200001][2];
//k等于0表示bob来取
void dfs(int f){
    if(!head[f]){
        dp[f][0]=dp2[f][0]=-c[f];
        dp[f][1]=dp2[f][1]=c[f];
        return ;
    }
    dp[f][0]=dp2[f][0]=1e13;
    dp[f][1]=dp2[f][1]=-1e13;
    for(int i=head[f];i;i=edge[i].ne){
        int to=edge[i].to;
        dfs(to);
        dp[f][0]=min(dp[to][0],dp[f][0]);
        dp[f][1]=max(dp[f][1],dp[to][1]);
    }
    dp2[f][0]=dp[f][1]-c[f];
    dp2[f][1]=dp[f][0]+c[f];
    dp[f][0]=min(dp2[f][0],dp[f][0]);
    dp[f][1]=max(dp[f][1],dp2[f][1]);
    return ;
}
int n;
int main(){
    scanf("%d",&t);
    while(t--){
        p=0;
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            head[i]=0;
        }
        for(int i=2;i<=n;++i){
            scanf("%lld",&c[i]);
        }
        for(int i=2;i<=n;++i){
            scanf("%d",&f);
            add(f,i);
        }
        dfs(1);
        printf("%lld\n",dp[1][1]);
    }
    return 0;
}