[P6623 [省选联考 2020 A 卷] 树](https://www.luogu.com.cn/problem/P6623)

给定一棵树上每个结点的权值 $v_i$ ,定义 $val_u$ 为 $u$ 的子树(含 $u$ )内的结点 $c_i$ 的 $v_{c_i}+d(c_i,u)$ 的异或和。求 $\sum\limits_{i=1}^nval(i)$ 。

首先很明显是从下往上递推,考虑怎么从儿子结点转移过来。

Part 1 传递答案

假设儿子 $v$ 的答案 $val_v=a_1\oplus a_2...\oplus a_k$ ,我们需要求 $val_v'=(a_1+1)\oplus (a_2+1)...\oplus (a_k+1)$的值。

因为是异或操作,想到使用 01Trie ,那么像常规 01Tire 一样记录每个结点被经过的次数 $cnt_r$ 。

过程中统计一下对应的 01Trie 里每一层里 1 的个数,就可以得到这一个点的答案了。

而由于由 $val_v$ 求 $val_v'$ 相当于给 01Trie 里的每个元素都 +1 ,那就把原数从低位到高位加入 01Trie ,都 +1 的话显然是影响到了当前末尾是 1 的数,它们都变成了 0 ,所以我们 交换0/1儿子的编号,不去改变对应的 $cnt$ 。

但是交换第一层的 01 儿子之后,想到后面如果有形如 "...11" 这样以若干个二进制 1 结尾的数,则还应该继续一路交换下去。注意交换之后也要修改一层内 1 的个数方便下一步计算。

显然要修改 $\log$ 次,所以这个操作是 $O(\log n)$ 的。

Part 2 统计答案

有了上面计算 $val_v'$ 的方法,需要考虑的就是怎么统计父节点 $u$ 的答案了。

先退一步想,可以暴力地对于每一个结点,都维护一棵 01Trie,每次把儿子的所有值 +1 插入,再把自己的 $v_i$ 插入统计每一层 1 的个数计算答案。

考虑优化这个过程,上面讲到了如果儿子结点已经建好了 01Trie ,怎么快速地得到所有元素 +1 后的 01Trie。那么我们只需要 合并 起来儿子结点的 01Trie ,再插入该节点的 $v_u$ ,就得到了它所对应的 01Trie。

考虑像线段树合并一样,合并两棵 01Trie ,只需要沿着根节点递归左右儿子,直到其中一棵没有对应结点就停止。代码长这样:

int merge(int r1,int r2){
    if(!r1||!r2)return r1|r2;
    cnt[r1]+=cnt[r2];
    c[r1][0]=merge(c[r1][0],c[r2][0]);
    c[r1][1]=merge(c[r1][1],c[r2][1]);
    return r1;
}

这样做看起来是很暴力的。那就来稍微看一下时间复杂度的问题。

只有两棵 Trie 里都有一样的元素 $a$ ,它才会每次合并贡献 $\log$ 的时间复杂度。

假设它出现了 $x$ 次,那就会在至多 $x$ 次合并里同时在两棵树里出现,对应的合并次数是 $\sum x=n$ 次,总时间复杂度是 $O(n\log n)$ 。

于是就可以写这道题了。dfs时每个节点建新 Trie ,和子节点合并,退出时执行 Part1 里的修改操作,递归回去即可。

完整代码Link

最后修改:2021 年 03 月 25 日 08 : 02 PM