AT_arc078_d

Apeiria_w · 2025-10-23 15:36:44 · 题解

爆标做法。

考虑求最终剩下的边权和的最大值。剩下的图的可以看作是 m 个块排成一条链，第 i 块向第 i+1 块有一条边 (u_i,v_i)，满足 u_1=1,v_{m-1}=n 并且 v_i=u_{i+1}。

考虑先求出一条 1\sim n 的路径，再枚举块，挂到路径内的点上。设 g_{S} 表示只考虑 S 内的点原问题的答案，显然要 1,n\in S。设 f_{S,i} 表示 1\sim i 的路径，经过 S 内的点的最大边权和。

先求出 f，让 g_S 的初值为 f_{S,n}。然后枚举 T\cap S=\empty 表示块内的点，再枚举一个 i\in S，表示要把这个块挂到 i 上，转移有 g_{S\cup T}\gets g_S+w_{T\cup\{i\}}。转移的过程中维护 h_{S,T}=\max_{i\in S} w_{T\cup\{i\}} 即可 O(1) 转移，复杂度 O(3^n)。

实现细节见 code