CF722 题解
[toc]
AC代码
A. Parsa’s Humongous Tree
给定一棵 $n$ 个点的树，树上每个点都有一个点权，对于一个点 $u$ ，它的点权 $val_u$ 取值范围是 $[l_u,r_u]$ 。树上每条边 $(u,v)$ 的边权是 $|val_u-val_v|$ ，询问边权之和的最大可能值。
$n\leq 2\times 10^5$ 。
一个贪心的猜想是：每个点 $u$ 的点权要么取 $l_u$ ，要么取 $r_u$ 。
根据这个猜想就能通过dp解决本题，令 $dp[u][0]$ 表示点 $u$ 取 $l_u$ 时的最大值，$dp[u][1]$ 表示点 $u$ 取 $r_u$ 时的最大值，那么转移式就是：
dp[u][0]=dp[u][0]+\max(|l_u-l_v|+dp[v][0],|l_u-r_v|+dp[v][1]) & (v是u的相邻子节点) \\
dp[u][1]=dp[u][1]+\max(|r_u-l_v|+dp[v][0],|r_u-r_v|+dp[v][1]) & (v是u的相邻子节点) \\
\end{cases}
B. Kavi on Pairing Duty
数轴上有 $2n$ 个点，你需要找出 $n$ 对不同的点对（每个点只能使用一次），使得任意两个点对 $(A,B)$ 都满足以下任意一个条件：
- 点对 $A$ 被 $B$ 完全包含（$A_L>B_L\cap A_R<B_R$）或点对 $B$ 被 $A$ 完全包含。
- 点对 $A$ 和 $B$ 覆盖的区间长度相等。
询问有几种不同的点对选择方案。
$n\leq 10^6$ 。
设 $dp[i]$ 表示 $i$ 对点对时的方案数，有两类不同的转移：
- 从 $dp[1],dp[2],\ldots,dp[i]$ 转移到 $dp[i+1]$
这类转移是比较容易想到的，以 $dp[i]$ 为例，我们可以直接在最外层嵌套一个点对：比如已有点对 $(2,3)(4,5)$ ，那我们可以直接在最外层框一个 $(1,6)$ 将内部完全包围。
-
所有数对等长
比如 $(1,2),(3,4),(5,6)$ 或者 $(1,4),(2,5),(3,6)$ 这些。对于任意一个 $i$ ，很快能发现这种情况的方案数就是 $d(i)$ ，$d(i)$ 表示 $i$ 的约数个数。这是因为，如果你想等分整段区间，那么点对长度必须是 $i$ 的因子。
综上，可以先预处理 $[1,n]$ 的 $d(i)$ ，然后利用前缀和优化dp，时间复杂度 $O(n)$ 。
C. Trees of Tranquillity
给定两棵大小为 $n$ 的树 $A$ 和 $B$ ，根据这两棵树构建一个点数为 $n$ 的图 $C$ ，该图中的两点 $u,v$ 当且仅当同时满足以下两项条件时连边：
- 在 $A$ 树中，点 $u$ 是点 $v$ 的祖先或者点 $v$ 是点 $u$ 的祖先。
- 在 $B$ 树中，点 $u$ 不是点 $v$ 的祖先并且点 $v$ 不是点 $u$ 的祖先。
询问图 $C$ 中的最大团大小。
$n\leq 3\times 10^5$。
观察可知：两条性质指的是点 $u$ 和 $v$ 在 $A$ 树的同一子树中，不在 $B$ 树的同一子树中；如果从最大团的角度考虑，最大团中的每个点在 $A$ 树中一定在一条根到叶子节点的链上，在 $B$ 树中则分别属于不同的子树（链）。
由于形成最大团的点一定是 $A$ 树中是链形的，所以考虑dfs序扫一遍 $A$ 树更新答案，因此问题就是：dfs序遍历 $A$ 树，每次加入一个节点 $u$ ，到达叶子节点时更新最大值，最大值等价于从根到当前叶子节点的链上最多有几个点在 $B$ 树中互不构成祖先，回溯时删除节点 $u$ 。
因此本题的难点就是如何求最大值，可以利用Euler Tour的性质来解决这一问题：
按照dfs序遍历一棵树，在进入一个点 $u$ 时打上时间戳 $in_u$ ，退出点 $u$ 时打上时间戳 $out_u$ ，那么点 $u$ 如果是点 $v$ 的祖先就必须满足：$ in_u<in_v<out_v<out_u $
也就是说 $[in_u,out_u]$ 完全包含区间 $[in_v,out_v]$ ，如果两个区间相离则点 $u$ 不是点 $v$ 的祖先。
Euler Tour的好处是：它是一个匹配的括号序列，于是不存在部分相交的区间，两个区间要么相互包含要么相互分离。因此根到当前叶子节点的链上最多有几个点在 $B$ 树中互不构成祖先这一问题可以转化为：根到当前叶子节点的链上最多有几个不相交区间 $[in_i,out_i]$ 。
利用线段树维护这一问题：当进入一个点 $u$ 时，单点修改 $in_i$ 的值为 $out_i$ ，然后进行判断：
- 当前区间被某一更大的区间包含：$[1,in_i]$ 中的最大值 $>out_i$ ，那么将这一更大的区间暂时消去（至多只会存在一个这种区间），因为当前区间更优；退出节点 $u$ 时需要恢复这个更大的区间。
- 当前区间不被某一更大的区间包含，但是当前区间内已经包含了较小的区间：该区间是更劣的区间，不需要更新。
- 当前区间不被某一更大的区间包含，且当前区间内不包含较小的区间：将这一节点加入最大团，答案 $+1$ 。
上方操作只需要维护：区间最大值+单点修改，因此普通线段树即可解决。