自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

搬运于2025-08-24 22:45:40，当前版本为作者最后更新于2023-03-08 21:14:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

• 原题链接

• 关于本题的一件趣事

---

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

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

$$Ans=\sum_{x \in S}\sum_{y \in T}f(x,y)-\sum_{x \in S}\sum_{y \in T }f(y,x)- \sum_{x \in S}w_x$$$$=\sum_{x \in S}(\sum_{y \in T}f(x,y)+ \sum_{y \in S}f(x,y) )-\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}sz_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;
}