Solution

A. King’s Tree

题目大意：\(n\) 个点的树，每条边上有一个整数 \(v_i\)。求字典序最小的路径 \((u,v)\) ，满足路径上所有边的乘积 mod \(10^6+3\) 为 \(K\)。

题解：点分治维护到每个重心的所有路径，有相同乘积时保留端点字典序最小的一个。 \(\mathcal{O}(n\log{n})\)。

B. LWDB

题目大意：\(n\) 个点的树，每个点初始颜色为 \(0\)。\(m\)次操作：

• 将点 \(v\) 半径 \(d\) 以内的点染为 \(c\)
• 询问点 \(v\) 的颜色

题解：把时间和颜色对应，询问即求能影响它的最大的时间。先建出点分树，然后在每个重心处维护一个单调栈（单减，key 为半径和对应的时间/颜色）。预处理点分树上每个点每个深度的祖先和到它的距离。

对于每次修改操作，从 \(v\) 开始往上修改 \(\log{n}\) 个重心，把本次染色在该重心处的半径压入单调栈中。

对于每次询问操作，从 \(v\) 开始往上查询 \(\log{n}\) 个重心，在单调栈中二分找到会影响 \(v\) 的修改，再将修改时间取 \(\text{max}\) 即可。

时间复杂度 \(\mathcal{O}(n\log^2{n})\)，空间复杂度 \(\mathcal{O}(n\log{n})\).

C. Decomposition

签到题。

D. Amazon River

题目大意：\(n\) 个点的树，\(1\) 号点黑色，其余点白色。\(m\) 次操作：

• 翻转点 \(v\) 的颜色
• 询问到点 \(v\) 最近的黑点的距离

题解：先建出点分树，在每个重心处维护一个 multiset 存所有子树中的黑点到重心的距离即可。

时间复杂度 \(\mathcal{O}(n\log^2{n})\)，空间复杂度 \(\mathcal{O}(n\log{n})\).

E. Minmax paths

题目大意：\(n\) 个点的树，每个点有一个权值 \(a_i\)。求：

\[ \sum_{i=1}^n\sum_{j=i}^n\left(\text{max}(i...j)-\text{min}(i...j)\right)\times \text{len}(i...j) \]

\(\text{max}(i...j),\text{min}(i...j),\text{len}(i...j)\) 分别为路径 \(i \rightarrow j\) 上的最大权值、最小权值和点数。

题解：可以 \(\text{max}\) 和 \(\text{min}\) 分开做，\(\text{min}\) 直接将权值取相反数之后按 \(\text{max}\) 做即可。

点分治，用权值线段树维护区间\(\sum \text{max}\)，\(\sum \text{len}\)，\(\sum \text{max}\times\text{len}\)，\(\sum 1\) 即可。

时间复杂度 \(\mathcal{O}(n\log^2{n})\)，空间复杂度 \(\mathcal{O}(n)\)。

F. Carpet

题目大意：\(n\) 个点的树，求一种方案，把每个点放入 \(10^6\times 20\) 的棋盘中，使得边不相交。

题解：轻重链剖分，重链放在同一列，轻链依次放在下一列。

G. Caves and Tunnels

裸题。

H. Tree Problem

题目大意：\(n\) 个节的树，每条边一开始都是黑边。\(m\) 次操作：

• 统计路径 \(u\) 到 \(v\) 中黑边的数量
• 将 \(u,v\) 路径上的边变成白色，路径上点的其他邻边变成黑色

题解：轻重链剖分，然后用两棵线段树分别维护轻重边。

对于重边：

• 在修改时，对于路径中的重边，在相应的线段树上进行区间修改使其变为白色，对于路径边缘的重边，在线段树上进行单点修改使其变为黑色。
• 在询问时，直接在相应的线段树上进行区间查询求得路径中的黑色重边数量。

对于轻边：

• 维护每个点被操作 \(2\) 影响的最晚时间 \(\text{opt}[x]\)，以及每条轻边被变成黑色的最晚时间 \(\text{last}[x]\)，那么每条轻边当前是黑色的充要条件就是 \(\text{last}[x] \ge \text{opt}[p[x]]\).
• 用线段树维护 \(\text{opt}[x]\)，则每次修改时只需要对路径中的点进行区间修改即可。
• 修改时只需要对 \(\log{n}\) 条轻边进行 \(\text{last}\) 修改，查询时在线段树中查询也是 \(\log{n}\)次

时间复杂度 \(\mathcal{O}(n\log^2{n})\).

I. Kindom and Roads

题目大意：\(n\) 个点的树，每个点有一个权值 \(w_i\)，初始没有任何边。接下来 \(n-1\) 次操作，每次增加一条边 \((a_i,b_i)\)，保证 \(a_i\) 与 \(1\) 连通，\(b_i\) 是一个单点。询问 \(1\) 到 \(a_i\) 路径上的逆序对数，并且将路径上所有点修改为 \(w_{b_i}\)。

题解：轻重链剖分，每个重链维护一个栈，存储该重链上压缩之后的权值段，深度较小的那端为栈顶。每次操作，我们从 \(a_i\) 往上爬，经过重链的时候弹出栈顶一段权值段，然后压入以 \(w_{b_i}\) 为权值的一段。然后对于弹出的所有权值段，暴力求一次逆序对。

每次操作最多增加 \(\mathcal{O}(\log n)\) 个权值段，那么一共有 \(\mathcal{O}(n\log n)\) 段。每次最多取出 \(n\) 段，所以总复杂度为 \(\mathcal{O}(n\log^2 n)\) ，空间复杂度 \(\mathcal{O}(n\log n)\) 。

J. Justified Jungle

题目大意：\(n\) 个点的树，输出所有的 \(k\) ，满足存在一种断边方式，使得断 \(k\) 条边之后的图每个连通块大小都相等。

题解：令 \(d = \frac{n}{k+1}\) ，如果 \(\text{size}\) 是 \(d\) 的倍数的子树有 \(k+1\) 个，那么这个 \(k\) 合法。