P9133 大富翁 题解

· · 题解

感觉挺神仙的，反正我是想不出来。

考虑游戏规则的实质。假设小 W 所选点集为 S，小 H 所选点集为 T，f(x,y) 在点 x 支配点 y 时为 1，其余为 0。则：

}f(y,x)- \sum_{x \in S}w_x )-\sum_{x \in S}(\sum_{y \in T}f(y,x)+ \sum_{y \in S}f(y,x) )- \sum_{x \in S}w_x -\sum_{x \in S}dep_x -\sum_{x \in S}w_x =\sum_{x \in S}(sz_x - dep_x - w_x)

于是贡献被拆分到每个点上，二人轮流从点权大的往点权小的选就为最优策略。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+10;
int n,w[N],p[N],dep[N],sz[N];
vector<int> vec[N];
inline void dfs(int u)
{
    sz[u]=1;dep[u]=dep[p[u]]+1;
    for(auto x:vec[u]) dfs(x),sz[u]+=sz[x];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&w[i]);
    for(int i=2;i<=n;i++) scanf("%d",&p[i]),vec[p[i]].push_back(i);
    dfs(1);for(int i=1;i<=n;i++) p[i]=i;
    sort(p+1,p+n+1,[](int a,int b){return sz[a]-w[a]-dep[a]>sz[b]-w[b]-dep[b];});
    long long ans=0;
    for(int i=1;i<=n;i++) if(i&1) ans+=sz[p[i]]-w[p[i]]-dep[p[i]];
    printf("%lld",ans);
    return 0;
}