task 1

独立考虑每个点权的移动路径 $x\to y$，那么至多往上移动一格，可以得到若干边是否要被操作。如果信息冲突则 $p\not\in S$。如果 $\text{lca}(x,y)=fa_x$ 则有 $(x,fa_x)$ 必须操作，$y$ 方向的子树中间这些边不能操作。到它时不断往下的路径有，在目标方向（不存在则是最后）前面的子树对应的边都不能操作。如果所有点权的路径信息都满足则 $p\in S$。

事实上根据树的性质，如果 $(u,fa_u)$ 两侧的初始点权集合和最终点权集合都不发生改变，那么 $(u,fa_u)$ 一定不被操作，否则一定被操作，这样得到一组断边方案，判定得到的 $p'$ 是否 $=p$ 即可。

刻画点权的交换/置换环

可以发现一组决策是否交换的方案与一个合法的 $p$ 一一对应，不存在算重。

考虑将所有操作的边染黑，那么黑边连接起来的若干连通块满足连通块之间的点权交换是独立的。令 $p_i$ 表示 $i$ 的点权来自于初始的 $p_i$，最终一个连通块会形成一个大的置换环。一个点 $u$ 向下的交换是一个环，然后每个子问题独立。

单独研究一个连通块：对于连通块上的非叶子节点 $u$，$p_u$ 为最后一个出边指向的点。对于叶子节点 $u$，不断往上跳父亲直到跳到根（此时 $p_u=rt$，满足 $u$ 是从 $rt$ 不断走第一个儿子走到的结果），或者 $x$ 不是 $fa_x$ 的第一个出边，这种情况下 $p_u$ 是 $fa_x$ 染黑出边中 $x$ 的前驱。可以发现就是按照反的 dfs 序从 $rt$ 开始走，$p_i$ 取环意义上的下一个点。

task 2

求后继考虑先求出 lcp，然后求出 lcp 后的一位，再对剩余部分求最小解。先得到一个 $O(poly(n))$ 的做法。

首先要最大化 lcp，做的子问题形如：$[1,x]$ 对应的 $p$ 限制必须被满足，$x+1$ 的 $p$ 可以取到一个集合中的点（权值大于原点权且未被前缀使用过），判定是否存在合法的 $p$。那么每条边就有三种状态：染白/染黑/待定。$[1,x]$ 每个限制都带来若干条边的限制被确定，且互相独立，必须互不冲突。求出对于 $x+1$ 合法的点集，找到优先级大于原点权且最小的。固定一个 $x$ 就是 $O(n)$ 的，这个子问题暂时是 $O(n^2)$。

由于每个限制基本是独立的，所以当前尽管只确定了若干条边，但是它们已经足够描述所有已经确认的限制，对于剩下未确定边全部染白就可以得到一组合法的解，说明了这样局部确认的正确性。

假装我们已经求出 lcp，现在需要对剩余部分求出最小解。逐位填写，考虑刻画出 $u$ 可行的 $p_u$ 的来源：

• 所有 $u\to p_u$ 路径覆盖的所有边必须不被染白。
• 若 $p_u$ 是 $u$ 的儿子：找到 $u$ 儿子中最后一个黑边，可行的 $p_u$ 即为 $fa_v=u$，$(u,v)$ 未被染白且顺序在最后一个确定黑边及以后的 $v$。
• 若 $p_u$ 是 $u$ 的祖先，必须有 $(p_u,fa_{p_u})$ 可以染白（或不存在），且 $u\to p_u$ 往上跳的路径中，对于 $x\ne p_u$ 一定有 $fa_x$ 中 $(x,fa_x)$ 的前面不存在某条边被确定染黑（否则与首条被遍历的限制冲突）。
• 若 $p_u$ 是 $u$ 祖先中它这个方向前面的某个儿子：假设 $\text{LCA}(p_u,u)=t$，那么设 $t$ 在 $u$ 方向的儿子为 $t'$，则 $u\to t'$ 有 $x\ne t'$ 满足 $(x,fa_x)$ 可能成为 $fa_x$ 的首个遍历边。对于 $t$ 必须有 $(p_u,t)$ 在 $(t',t)$ 前面且中间所有边不能有黑的，在这之后都染白。

这样就 $O(n)$ 刻画出了可行范围，可以做到 $O(n^2)$。注意到对于最后一类，如果找到祖先中第一个前面有黑边的点，那么上面就一定不可行了，而且前面都不存在黑边，就可以快速刻画出这个取值范围。

使用重链剖分优化这个过程，确认一个 $p$ 之后对若干边执行染色操作，就可以做到 $O(n\log^2n)$。每个节点维护一个序列并查集或者 set 来支持染色，对于向上的祖先链拆为若干重边和轻边，轻边暴力而重边统一处理。