2025CCFCAT省赛-D.简单树上问题（位运算，树）

自从打完ZCPC后就没怎么好好地做过题了，当然也没有好好写过题解。话说脑子偷懒多了真的会变笨吗。为了防止自己变笨，最终还是说服了自己来写这篇题解。

题目

给定一棵 n 个节点的有根树，节点编号为 1 到 n ，根节点为 1 。每个节点有一个非负整数权值，节点 i 的权值初始为 ai 。

你可以进行若干次操作。在一次操作中，你可以选择任意一个节点 u 和一个非负整数 x ，随后将 u 及其子树中所有节点的权值按位异或∗ 上† x ，这次操作的代价为 sizu 和 x 的乘积，其中 sizu 表示以 u 为根的子树的大小（即节点个数，包括 u 本身）。

你的目标是通过若干次操作，将所有节点的权值变为 0 。请你计算一下，代价的总和最小是多少？

Input

第一行一个整数 n （2≤n≤105 ），表示树的节点数。

第二行 n 个整数 a1,a2,⋯,an （0≤ai<230 ），表示每个节点的初始权值。

第三行 n−1 个整数 fa2,fa3,fa4,⋯,fan （1≤fai<i ），分别表示节点 2,3,4,⋯,n 的父亲节点的编号。

输入数据保证这是一棵树。

Output

输出一个整数，表示将所有节点权值变为 0 的最小总代价。

样例

8
0 1 2 34 56 78 910 1112
1 1 2 2 3 4 4

2333

题解

题目大意

给定一棵树，可以随意地对子树所有节点对一个任意的数字x进行异或，代价是sizu×x。求让所有节点权值为零的最小代价。

思路

有两种想法，自下而上或自上而下。

自下而上无疑是困难的，对上面的节点操作会影响下面的节点。为了最后所有权值为0，还不得不使处理的子树所有节点权值一样。

自上而下处理，每次的x为当前节点权值是可行的。因为这样保证了对于每个节点只计算一次代价。假如对某个节点u异或了c1、c2….ck使它为0，而$\bigoplus_{i=1}^k c_i \le siz_u \times \sum_{i=1}^k c_i。则对于一个节点，能够单次操作使它为。则对于一个节点，能够单次操作使它为0$一定是最优的。

那么想法就很明确了。dfs处理出子树大小siz，再dfs处理每一个节点，每个节点只处理一次。

需要注意的是每次操作会影响下面的节点，所以dfs的时候向下传递所有x的连续异或，子节点更新为异或x的连续异或，并不断更新向下传递的x。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5+5;
array<int, maxn> a;
vector<int> e[maxn];
int res = 0;
array<int, maxn> s;
void dfsu(int p){
    int cnt = 0;
    for(int i:e[p]){
        dfsu(i);
        cnt+=s[i];
    }
    cnt++;
    s[p] = cnt;
}
void dfs(int p, int x){
    a[p] = a[p]^x;
    res += s[p]*a[p];
    for(int i:e[p]){
        dfs(i, x^a[p]);
    }
}
signed main(){
    int n;
    cin >> n;
    for(int i=1;i<=n;++i) cin >> a[i];
    for(int i=2;i<=n;++i){
        int f;
        cin >> f;
        e[f].push_back(i);
    }
    dfsu(1);
    dfs(1, 0);
    cout << res;
    return 0;
}