做题记录 25.10.12

· · 个人记录

QOJ #6298. Coloring

a_i$ 向 $i$ 连边，构成外向基环树，则操作等价于每次选择一条边 $u\to v$，令 $c_u\to c_v

令 t_u 表示结点 u 的 c 的变化次数

显然有 \forall (u\to v),t_v\le t_u

令 dp_{u,i} 表示基环树的子树 u 中，t_u=i 时，子树内的最大贡献

显然 dp_{u,i}\gets ((i+[u=s])\bmod 2)w_u-ip_u，dp_{u,n+1}\gets -\infty，每加入一个儿子 v 使 dp_{u,i}\gets dp_{u,i}+ \max_{j=0}^{i+[u=s]} dp_{v,j}，前缀 \max 优化可做到 O(n^2)

当 s 在树部分上时，受其父亲影响点 s 至多变化一次，因此答案为 \max(dp_{s,0},dp_{s,1})（此时显然可以做到时间复杂度 O(n)，但意义不大）

当 s 在环上时，特判环长为 2 的情况：设另一个点为 t，则 s,t 之间要么不操作 s 和 t，状态为 1,0，要么操作 s\to t 变为 1,1，要么操作 t\to s 变为 0,0，对应的操作数量为 (0,0),(0,1),(1,0)，因此此时答案为 \max(dp_{s,0}+dp_{t,0},dp_{s,0}+dp_{t,1},dp_{s,1}+dp_{t,0})

当环长 >2 时，设环上的点为 p_{1\sim l}，其中 p_1=s，且认为此时初始的 t_s=1，则显然有 t_{p_{1\sim l}} 单调不增，可证 t_{p_l}\ge t_s-2

因此枚举 k=1\sim n+1，令 g_{i,0/1/2} 表示 p_{1\sim i} 中 t_{p_i}=t_s-0/1/2 时最大的贡献，则

g_{1,0}\gets dp_{s,k-1}\\ g_{i,j}\gets \max g_{i,0\sim j}+dp_{t_i,j}

用 \max g_{l,\ast} 更新答案即可

总时间复杂度 O(n^2)

代码

参考