官方题解只能做到 $O(n^2)$？玩的太差了。这题可以做到 $O(n\log n)$ 摊还时间、$O(n)$ 空间。关键不只是优化环上的枚举：树形动态规划中看似需要保留的 $O(n)$ 个“变色次数”状态，也能压缩维护。达到这一复杂度需要使用支持整体平移的可合并字典；普通平衡树配合分段合并可以得到较容易实现的 $O(n\log^2 n)$ 版本，但不能直接把它算成 $O(n\log n)$。
题目中只有 $s$ 初始为 $1$，一次操作令 $c_i\leftarrow c_{a_i}$，费用为非负的 $p_i$，最终收益为所有颜色为 $1$ 的点权之和减去操作费用。数据范围为 $n\le 5000$，但下面的算法不依赖平方级状态数。
一、把操作序列变成整数标号
建立传播方向的边 $a_i\to i$。从 $s$ 沿这些边不可达的点永远不能变成 $1$，可以直接忽略。剩下的图只有两种形态：以 $s$ 为根的一棵树，或者包含 $s$ 的一个有向环及其外向树。
首先不能假设每个点只变色一两次。例如，一个可以反复传递颜色的环外接一条正负点权交替的链，就可能需要多轮传播，才能保留链上的多个正权点，同时清除中间的负权点。
删掉所有不改变颜色的操作。设点 $i$ 实际变色 $q_i$ 次，定义 $h_s=q_s+1$，其他点定义 $h_i=q_i$。于是所有点最终的颜色统一等于 $h_i\bmod 2$，总收益统一写成 $p_s+\sum_i\bigl(w_i(h_i\bmod 2)-p_i h_i\bigr)$。
这些标号满足：$h_s\ge 1$，其他标号非负；对于 $i\ne s$，有 $h_i\le h_{a_i}$；对于 $s$，有 $h_s\le h_{a_s}+2$。
原因是，一个初始为 $0$ 的点要依次变成 $1,0,1,0,\ldots$，父亲就必须依次提供这些颜色。$h_s$ 中额外加入的 $1$，恰好把 $s$ 初始提供的颜色也计算进去。
如果 $s$ 不在环上，那么 $a_s$ 永远为 $0$，所以 $h_s$ 只能为 $1$ 或 $2$：分别对应始终保留 $s$，以及最后清除 $s$。这时只需要两个状态的树形动态规划，可以在线性时间解决。
下面考虑 $s$ 在长度为 $m\ge 3$ 的环上。按照传播方向将环写成 $v_0=s,v_1,\ldots,v_{m-1}$，即 $a_{v_i}=v_{i-1}$，$a_s=v_{m-1}$。令 $H=h_s$，环上的约束就是
$H=h_{v_0}\ge h_{v_1}\ge\cdots\ge h_{v_{m-1}}\ge H-2$。
因此，环上的标号只能是连续三段 $H,H-1,H-2$，允许某些段为空。
当环长至少为 $3$ 时，这些条件不仅必要，而且充分。
环上的所有 $1$ 始终构成一个连续区间。区间前端向前走一步，就是把一个 $0$ 变成 $1$；区间后端向前走一步，就是把一个 $1$ 变成 $0$。给定上述标号，所有染成 $1$ 的操作分别构成前端运动序列的一个前缀，所有清除操作分别构成后端运动序列的一个前缀。
设需要执行的两类操作数量分别为 $A,B$，最终环上有 $L$ 个 $1$，则 $L=1+A-B$。如果 $L\ge 1$，先执行 $B$ 次“扩张一步，再收缩一步”，最后再扩张 $L-1$ 步；如果 $L=0$，先执行 $A$ 次这样的往返，最后收缩一次。往返过程中区间长度只在 $1,2$ 之间变化，由于 $m\ge 3$，不会提前变成全 $0$ 或全 $1$。
挂在环上的树也没有额外障碍：在父亲依次提供的颜色阶段中，让儿子完成前 $h_i$ 次变色即可，并在父亲进入下一阶段前递归处理其后代。因此，原问题已经精确转化成了上述整数标号优化问题。
长度为 $2$ 的环需要单独处理，因为两个环点一旦同色，就再也不能改变环上的颜色；后面会给出公式。
二、树形动态规划：维护两条单调差分序列
对于一个初始为 $0$ 的非环点 $u$，定义 $F_u(k)$ 为：在 $h_u\le k$ 的限制下，整棵子树能够取得的最大收益，其中已经扣除了子树内全部操作费用。
显然 $F_u(0)=0$，并且
$$ F_u(k)=\max_{0\le t\le k} \left( w_u(t\bmod 2)-p_u t+\sum_{v\in\operatorname{child}(u)}F_v(t) \right). $$
直接保存整张表会得到平方级算法。我们不保存函数值，而保存它的差分。
令 $\Delta_u(k)=F_u(k)-F_u(k-1)$，再按奇偶拆成 $O_u(j)=\Delta_u(2j-1)$ 和 $E_u(j)=\Delta_u(2j)$，其中 $j\ge 1$。
下面的性质是整个优化的核心：
$O_u$ 和 $E_u$ 都是非负、单调不增、最终为零的序列。
这里不是说整个差分序列单调。例如，差分可以是 $[10,0,10,0,10,0,\ldots]$，但拆开奇偶后，两条序列分别单调。
先把所有儿子的状态合并，记 $X(j)=\sum_v O_v(j)$，$Y(j)=\sum_v E_v(j)$。考虑尚未取前缀最大值的函数 $G(k)=\sum_vF_v(k)+w_u(k\bmod 2)-p_u k$，它在奇数、偶数位置的增量分别为 $\alpha_j=X(j)+w_u-p_u$、$\beta_j=Y(j)-w_u-p_u$。
根据归纳假设，$\alpha$ 和 $\beta$ 分别单调不增。我们要做的，就是从 $G$ 得到它的前缀最大值 $F_u$。
在第一个负增量出现之前，$G$ 一直不下降，因此它的每一步增量直接成为 $F_u$ 的增量。第一个负增量出现之后，同一奇偶类的增量永远为负，于是只剩另一奇偶类的位置可能刷新最大值。这恰好给出两种转移。
第一种：第一个负增量是 $\alpha_t$，出现在位置 $2t-1$。
对于 $j< t$，保留 $O_u(j)=\alpha_j$、$E_u(j)=\beta_j$。对于 $j\ge t$，有 $O_u(j)=0$，而 $E_u(j)=\max{0,X(j)+Y(j)-2p_u}$。
这是因为此后每个奇数位置都不优于前一个偶数位置，所以只需比较相邻偶数位置；两步合起来的增量就是 $\alpha_j+\beta_j$。
第二种：第一个负增量是 $\beta_t$，出现在位置 $2t$。
对于 $j< t$，保留 $E_u(j)=\beta_j$，之后令 $E_u(j)=0$。对于 $j\le t$，保留 $O_u(j)=\alpha_j$；对于 $j>t$，有 $O_u(j)=\max{0,X(j)+Y(j-1)-2p_u}$。
此时只需比较相邻奇数位置，两步合起来的增量是 $\beta_{j-1}+\alpha_j$。
两种转移中的后缀都单调不增；在前后缀交界处，新的增量是在原本不增的增量上又加了一个负数，也不会上升。由此同时证明了转移和奇偶差分的单调性。如果 $w_u=p_u=0$，则没有必要寻找负增量，直接令 $O_u=X$、$E_u=Y$。其他情况下至少有一类增量最终为负。
接下来要把这些序列操作真正做到对数时间。
对任意单调不增、最终为常数 $b$ 的阶梯函数 $X$，只保存它的下降位置及下降量。记 $d_t=X(t)-X(t+1)>0$，则 $X(j)=b+\sum_{t\ge j}d_t$。正常的动态规划状态中 $b=0$；计算中间状态时允许 $b$ 为负数。
于是，函数逐点相加就是合并两份以 $t$ 为键、以 $d_t$ 为附加值的字典，同一个键的下降量相加。整体加常数只需修改 $b$。函数横向平移一步，只需将所有下降位置整体平移一步。
切分、拼接也只需要常数次字典操作。例如，在位置 $q$ 后，把函数 $P$ 的前缀和函数 $Q$ 的后缀拼接起来，只需保留 $P$ 中键小于 $q$ 的下降点，保留 $Q$ 中键大于 $q$ 的下降点，再在 $q$ 处放入下降量 $P(q)-Q(q+1)$。我们的转移已经保证结果单调，所以这个下降量非负。
把函数截成 $\max(0,X)$，只需找到它第一次不为正的位置，删除后面的下降点，并修正一个边界下降量。这个位置应该利用子树下降量之和直接查找，而不是在对数时间的点查询外再套一层二分。 因为 $X(j)=X(1)-\sum_{t< j}d_t$，所需查询本质上就是按累计下降量做一次选择。
现在回看两类转移：它们只会切开 $X,Y$，保留两个前缀，把需要的两个后缀相加，必要时将一个后缀平移一步，再截去非正部分。没有复制整段序列，也没有逐项扫描后缀。每个顶点只需要常数次切分、合并、平移及边界修改。
所需的数据结构正是 mergeable dictionaries with shifts。Bille、Ettienne 和 Gørtz 给出了基于偏置搜索树的实现，支持任意交错键集合的合并、切分、查找和整体平移，所有操作均为 $O(\log U)$ 摊还时间，其中 $U$ 是键所在整数值域的大小。这里必须支持任意交错合并，不能用普通平衡树的有序拼接代替。([arXiv][2])
在该结构上额外维护 $\sum d_t$ 和 $\sum t d_t$，即可支持上述累计下降量查询。相同键合并时将附加值相加；论文中的结构本身也允许保存同键的重数，这类附加信息不会改变其操作复杂度。([arXiv][3])
为了确定值域，设 $\ell_u$ 是 $u$ 子树的最大根叶路径长度，按点数计算。则 $F_u(k)$ 在 $k\ge\ell_u$ 后一定不再变化：对任何最终颜色方案，从叶子向上，将每个标号改为“不小于所有儿子标号、且奇偶性正确的最小非负整数”，就能使 $h_u\le\ell_u$，而且不会增加费用。
因此所有下降位置都在 $O(n)$ 的整数值域内。整棵森林总共执行 $O(n)$ 次字典操作，每个顶点只增加常数个边界下降点，合并和切分不会凭空复制下降点。所以，全部树形动态规划共需 $O(n\log n)$ 摊还时间、$O(n)$ 空间。儿子的结构并入父亲后不再保留历史版本。
普通平衡树配合分段合并也能完成同一套转移，但直接得到的保证是每次操作 $O(\log n\log U)$ 摊还时间，即本题的 $O(n\log^2 n)$；去掉这一额外对数，需要上述偏置树版本。([arXiv][3])
三、环上只做线性个更新，而不是逐轮扫描整个环
对每个环点 $v$，合并它的所有非环儿子，得到 $B_v(k)=\sum_uF_u(k)$。它表示环点标号为 $k$ 时，所有挂树的最优贡献，不包含环点自身。
令 $d_v$ 为这些挂树的最大高度，没有挂树时为 $0$。那么 $B_v(k)$ 在 $k\ge d_v$ 后恒定，而且 $\sum_v d_v\le n-m$，因为不同环点的挂树互不相交。
因此，可以将每个 $B_v(0),B_v(1),\ldots,B_v(d_v)$ 显式取出，所有数组的总长度仍然只有 $O(n)$。由奇偶差分恢复函数值也很直接：$F(k)=\sum_{j=1}^{\lceil k/2\rceil}O(j)+\sum_{j=1}^{\lfloor k/2\rfloor}E(j)$。对下降点表示的序列，有 $\sum_{j=1}^{r}X(j)=br+\sum_t d_t\min(r,t)$，用刚才维护的两个子树和即可在 $O(\log n)$ 时间查询。所以这一步总共仍是 $O(n\log n)$。
记 $D=\max_v d_v$，以及环上费用之和 $P=\sum_{v\text{ 在环上}}p_v$。
只需考虑 $1\le H\le D+3$。因为当 $H\ge D+4$ 时，可以将所有环点的标号同时减去 $2$：奇偶性不变，所有挂树仍处于饱和范围，收益不变而费用减少 $2P\ge 0$。不断这样处理，就能把 $H$ 降到上述范围。
固定一个 $H$，用偏移量 $r_v=H-h_v$ 表示环点标号。我们需要 $r_s=0$，其他偏移量属于 ${0,1,2}$，并且沿传播方向单调不减。
把所有环点共同的费用项 $-HP$ 提出来，定义
$C_{v,r}(H)=B_v(H-r)+w_v((H-r)\bmod 2)+r p_v$。
接下来就是三个状态的链上动态规划。对 $v\ne s$，建立一个 $3\times3$ 的最大加法矩阵 $M_v$：当 $x\le y$ 时，令 $M_v[x,y]=C_{v,y}(H)$；否则令它为 $-\infty$。矩阵乘法定义为 $(A\otimes B)[x,z]=\max_y(A[x,y]+B[y,z])$，恰好表示前后两段动态规划的合并。
若 $Q(H)=M_{v_1}\otimes\cdots\otimes M_{v_{m-1}}$，那么固定 $H$ 的最优答案为
$$ V(H)=p_s-HP+C_{s,0}(H)+\max_{r\in\{0,1,2\}}Q(H)[0,r]. $$
用线段树维护这个矩阵乘积，单点修改需要 $O(\log m)$ 时间，读取整环答案只需 $O(1)$ 时间。
如果对每个 $H$ 都修改所有矩阵，仍然是平方级。最后一个优化是：分别扫描奇数 $H$ 和偶数 $H$，每次增加 $2$。
这样环点权对应的奇偶性不变，$r p_v$ 也不变，矩阵中只有 $B_v(H),B_v(H-1),B_v(H-2)$ 可能变化。当 $H\ge d_v+2$ 后，这三项全部饱和，之后这个环点的矩阵就再也不需要修改。
因此，对每个环点，直接把“可能需要修改它的 $H$”放入对应桶中即可。这些事件的总数是 $O\bigl(\sum_v(d_v+1)\bigr)=O(n)$，并不是 $O(nD)$。每个事件做一次线段树单点修改，整个环上的处理就是 $O(n\log n)$。
实际可以分别从 $H=2$ 和 $H=3$ 开始扫描两种奇偶性；$H=1$ 单独在线性时间计算。此时只允许偏移量 $0,1$，也就是环上从 $s$ 开始的一段前缀标号为 $1$，剩下的标号为 $0$，取最大前缀收益即可。
最后补全两个边界情形。
$s$ 不在环上。 只计算每个非根点的 $F_u(1),F_u(2)$。其中 $F_u(1)=\max{0,w_u-p_u+\sum_vF_v(1)}$，$F_u(2)=\max{F_u(1),-2p_u+\sum_vF_v(2)}$。答案是 $\max{w_s+\sum_vF_v(1),-p_s+\sum_vF_v(2)}$，总时间 $O(n)$。
$s$ 在二元环上。 设另一个环点为 $t$，环上只有三种有意义的操作过程：不操作环点，清除 $s$，或者染色 $t$。对应答案分别为 $w_s+B_s(1)$、$-p_s+B_s(2)$、$w_s+w_t-p_t+B_s(1)+B_t(1)$，取最大值即可。同样只需要挂树的两个状态，可以在线性时间处理。
注意，全局答案不一定非负，不能初始化为 $0$：让所有点最后为 $0$ 也可能需要支付费用。
综上，找出有效部分需要 $O(n)$ 时间；奇偶差分的树形动态规划需要 $O(n\log n)$ 摊还时间；展开所有环点的有效收益表需要 $O(n\log n)$ 时间；环上的事件扫描也只需要 $O(n\log n)$ 时间。最终得到 $O(n\log n)$ 摊还时间、$O(n)$ 空间。