XXI Open Cup named after E.V. Pankratiev. Grand Prix of Suwon

发表于 分类于

XXI Open Cup named after E.V. Pankratiev. Grand Prix of Suwon 题解。

A. Another Tree Queries Problem

以 $1$ 为根，考虑询问中每条边对答案的贡献。

分两种情况：子树和，总和-子树和。

总和-子树和的点出现在 $u$ 到 $1$ 的路径中。

因此答案为 $dep_u\times \sum a_i +\sum sum_u-2\times \sum_{v\in(u,1)}sum_v$，其中 $sum_u$ 表示 $u$ 子树的节点的 $a_i$ 的和。

树剖，用线段树维护 $sum_u$。

对于子树 $u$ 内加 $x$，子树内的点的 $sum$ 各自加上其子树大小 $\times x$，$fa_u$ 到 $1$ 的节点，$sum$ 加上 $siz_u\times x$。

对于链 $(u,v)$ 内加 $x$，链上的点的 $sum$ 加一个公差为 $1$ 的等差数列。可用 $+dep_w$ 维护。$lca_{u,v}$ 到 $1$ 的节点，$sum$ 加上 $(u,v)$ 间点的个数乘以 $x$。

于是用线段树维护，区间加，区间加 $siz_u$，区间加 $dep_u$ 即可。

一堆细节，极其容易写错。。。

B. Best Meeting Places

从小到大排序，用并查集维护即可。

C. Colorful Squares

二分答案，扫描线，用线段树维护当前覆盖某个节点的颜色数。

唯一麻烦的是修改，需要确定哪些点需要被修改。

显然，需要修改的是一段区间，对于每个颜色，开一个set记录当前的点，然后通过查找前驱后继找到这个区间。

时间复杂度 $O(n\log^2n)$。

E. Expected Distance

两点距离为 $dis_{1,u}+dis_{1,v}-2\times dis_{1,lca(u,v)}$。

由期望线性性，我们将上面拆成三部分，前两部分的 $dis_{1,i}$ 的期望值可以通过递推计算，设为 $f_i$。

而对于 $u,v(u<v)$ 而言，我们需要求出 $dis_{1,lca(u,v)}$ 的期望值：

  • 对于 $v$，选择 $v$ 的一个父亲 $i$，概率为 $\frac{a_i}{\sum_{j=1}^{i-1}a_j}$。
  • 如果 $i=u$，则表示找到了 $lca$，返回 $f_u$。
  • 如果 $i>u$，则令 $u’=u,v’=i$，继续递归。
  • 否则 $i<u$，则令 $u’=i,v’=u$，继续递归。

可以发现，$lca(u,v)$ 必须 $\le u$。因此， $dis_{1,lca(u,v)}$ 的期望和 $v$ 没有任何关系。设 $g_u$ 为此时的期望值，则有：$g_u=\frac{a_uf_u+\sum_{j=1}^{u-1}a_jg_j}{\sum_{j=1}^ua_j}$，也可以递推求出。

时间复杂度 $O(n+q)$。

F. Find the XOR

首先根据经典结论，两点间的异或和可以看成随便一棵生成树中两点走树边的异或和再异或上若干个环的值。

环的异或值一共有 $m-n+1$ 个，将这些数扔进线性基 $Base$ 里。

设 $f(x),g(x)$ 为 $x$ 经过 $Base$ 后的最小值，最大值。

那么答案就是 $\oplus_{l\le i<j\le r}g(d_i\oplus d_j)$。 我们要想办法将这个 $d_i,d_j$ 拆到外面去，否则就无法快速算了。最大值 $g(x)$ 比较难拆开，那么来看看 $f(x)$。

运用了线性基的若干重要性质：

  • 首先，$f(x)\oplus g(x)$ 等于 $Base$ 中能异或出的最大值。考虑用归纳证明即可。那么可以将 $g(x)$ 转换成 $f(x)$ 了。
  • 对于 $f(x)$，有 ：$f(x)\oplus f(y)=f(x\oplus y)$。

那么，经过这些转化后就比较简单了。