树上问题

Archaeology

非常简单，前几天刚做了 [JOISC 2023 Day3] Tourism，这就是个弱化版，直接用 set 维护前驱后继，计算虚树大小就行。

Surprise me!

神仙题，把莫反，虚树，dp 完美结合在一起。

首先这个式子一看就不能做，要想办法推一下，突破点在欧拉函数，但是函数里带的是点权不好做，所以对排列求逆，把 \(\sum\limits_{i=1}^n\sum\limits_{j\not=i} \phi(a_ia_j)dis(i,j)\) 变为 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^n \phi(ij)dis(b_i,b_j)\)。

\(i,j\) 在一起肯定不能拆贡献，下一步把 \(\phi(ij)\) 拆开，变成 \(\frac{\phi(i)\phi(j)\gcd(i,j)}{\phi(\gcd(i,j))}\)，接着莫反。

\(\begin{alignedat}{3} &\sum_{i=1}^n\sum_{j=1}^n\frac{\phi(i)\phi(j)\gcd(i,j)}{\phi(\gcd(i,j))}dis(b_i,b_j)\\ =&\sum_{d=1}^n\frac{d}{\phi(d)}\sum_{i=1}^n\sum_{j=1}^n\phi(i)\phi(j)[\gcd(i,j)=d]dis(b_i,b_j)\\ =&\sum_{d=1}^n\frac{d}{\phi(d)}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\phi(id)\phi(jd)[\gcd(i,j)=1]dis(b_{id},b_{jd})\\ =&\sum_{d=1}^n\frac{d}{\phi(d)}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\phi(id)\phi(jd)dis(b_{id},b_{jd})\sum_{x|i,x|j}\mu(x)\\ =&\sum_{d=1}^n\frac{d}{\phi(d)}\sum_{x=1}^n\mu(x)\sum_{i=1}^{\lfloor\frac{n}{dx}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{dx}\rfloor}\phi(idx)\phi(jdx)dis(b_{idx},b_{jdx})\\ =&\sum_{T=1}^n\sum_{d|T}\frac{d\mu(\frac{T}{d})}{\phi(d)}\sum_{i=1}^{\lfloor\frac{n}{T}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{T}\rfloor}\phi(iT)\phi(jT)dis(b_{iT},b_{jT}) \end{alignedat}\)

于是可以枚举 \(T\)，前半部分可以线性筛后枚举 \(d\) 的倍数 \(O(n\log n)\) 预处理，后半部分把 \(a_i\) 是 \(T\) 的倍数的点拉出来建虚树，总共会有 \(O(n\log n)\) 个点。

对于每棵虚树，我们要算 \(\sum_{i=1}^x\sum_{j=1}^x w_iw_jdis(i,j)\)，其中 \(w_i\) 是点权，考虑 dp，把转移式写出来。

\(\begin{alignedat}{3} f_u&=f_u+f_v+\sum_{i\in U}\sum_{j\in V} w_iw_jdis(i,j)\\ &=f_u+f_v+\sum_{i\in U}\sum_{j\in V} w_iw_j(dis(i,u)+dis(j,v)+len(u,v))\\ &=f_u+f_v+\sum_{i\in U}\sum_{j\in V} w_iw_jdis(i,u)+w_iw_jdis(j,v)+w_iw_jlen(u,v)\\ &=f_u+f_v+\sum_{j\in V} w_j\sum_{i\in U}w_idis(i,u)+\sum_{i\in U} w_i\sum_{j\in V}w_jdis(j,v)+len(u,v)\sum_{i\in U}w_i\sum_{j\in V}w_j\\ &=f_u+f_v+h_vg_u+h_ug_v+len(u,v)h_uh_v\\ g_u&=g_u+g_v+h_vlen(u,v)\\ h_u&=h_u+h_v \end{alignedat}\)

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

Groceries in Meteor Town

既然要算路径上的边权最小值，那么先建出 Kruskal 重构树，然后考虑答案就是 \(x\) 与每个白点 lca 的深度最小的点的点权。

我们知道，这个点就是 \(x\) 与所有白点的 lca 的 lca，那么用线段树维护全局 lca 即可。

复杂度 \(O(n\log n)\)。

Campus

发现由于有清零操作，离线比较好做，考虑对两个集合分别建树，然后考虑清零操作相当于对与一个点只有 \([l,r]\) 内的加操作有用，那么先 dfs 第二棵树，用 set 找到一个询问的有效时间，然后 dfs 第一棵树，用树状数组维护时间 \(t\) 时的加法，查询操作相当于区间求和。

只用到并查集和树状数组，复杂度 \(O(n\log n)\)。

Clockwork Bomb

不如第二道，但是构造方案很有启发性。

首先两边都连对的边没必要删，可以缩点，接下来就是找一个不用额外操作并且合法的操作序列。

考虑要求不成环，那么我们在两棵树上都以 \(1\) 为根，从叶子开始删点，然后加到这个叶子应该的父亲上，接着就可以不考虑这个叶子了。

因为我用了 set 判合法边，所以复杂度 \(O(n\log n)\)。

Cow and Vacation

水黑，倍增边长可以借鉴。

考虑一个关键点的控制范围是 \(\frac{m}{2}\)，如果两个关键点的控制范围有交那么可以合并，于是分为两种情况：

第一种，两个点可以直达。

第二种，两个点分别向对方跳 \(\frac{m}{2}\) 步，看是否在一个并查集中。

\(m\) 是奇数时不好操作，所以倍增边长，把 \(\frac{m}{2}\) 都变成 \(m\)。

关于控制范围是 \(m\) 为什么不行：我们没办法快速对每个关键点找询问点，询问点找关键点又无法精准定位，所以只能双向奔赴。

String Transformation 2

神秘题。

显然可以抽象成一个字符向另一个字符连边，找到一个加边序列，使得有所有合法的时间递增的路径。

关于如何找边数最少，有一个神秘方法：

首先每个连通块单独考虑，最多要 \(2n-1\) 条边，也就是绕两圈。

然后发现如果某些点之间不成环，那么就可以不用多绕一圈，那么找出最大 DAG 导出子图，大小为 \(m\)，答案就是 \(2n-m-1\)。

然而还是不太理解证明。

Mirror Box

神仙题 \(+1\)。

把 \((n+1)\times(m+1)\) 个点黑白染色，镜子相当于连边，由于不能有封闭空间，所以黑白生成图都不能有环。

然后考虑光线射到相邻位置，发现黑白生成图必须有一个是生成树，否则整个图一定能断成两部分，导致一条光线穿过。

接着发现一种颜色确定为生成树后另一种只有唯一方案，于是只需要用矩阵树定理求生成树数量即可。

Matches Are Not a Child's Play

考虑一次修改只会对修改前后的两个根及它们之间的路径有贡献。