2024 杭电多校 9

Problems	AC
1001. 树异或价值	⊕
1002. 树上询问	⊕
1003. 黑洞合并	○
1004. 亡语
1005. 怪物猎人	○
1006. 融合矿石
1007. 小猫钓鱼	○
1008. 最佳选手
1009. 长期素食
1010. 收集签名
1011. 地牢谜题：更高还是更低
1012. 地牢谜题：三个怪人

1001 树异或价值

学到了拆 dep，算 dep 次相当于从这个点往上每个点算一次

$$
\sum_{i=1}^n \sum_{j=1}^n\left(a_i \oplus a_j\right) \times \operatorname{dep}_{L C A(i, j)}
$$

$$
=\sum_{i=1}^n \sum_{j=1}^n\left(a_i \oplus a_j\right) \sum_{x=1}^n[i \in \operatorname{subtree}(x)][j \in \operatorname{subtree}(x)]
$$

$$
=\sum_{x=1}^n \sum_{i \in \text { subtree }(x)} \sum_{j \in \text { subtree( } x)}\left(a_i \oplus a_j\right)
$$

1005 怪物猎人

我草，赛时乱冲了 10 发，然后发现 read 没开 long long

1007 小猫钓鱼

我草，赛后才发现每个数最多才出现两次

赛时读错题了，写了个 plus 版本，但是过了