吃到大份了．
发现相邻交换和包含 1 , n 1, n 1 , n Δ \Delta Δ ( 1 , i ) , ( i , n ) , ( i , i + 1 ) (1, i), (i, n), (i, i + 1) ( 1 , i ) , ( i , n ) , ( i , i + 1 ) 1 < j < i < n 1 < j < i < n 1 < j < i < n i − j > 1 i - j > 1 i − j > 1 ( i , j ) (i, j) ( i , j )
考察交换后序列价值和原序列价值的差 Δ \Delta Δ l i = a i − 1 , r i = a i + 1 , o i = ∣ l i − a i ∣ + ∣ r i − a i ∣ l_i = a_{i - 1}, r_i = a_{i + 1}, o_i = |l_i - a_i| + |r_i - a_i| l i = a i − 1 , r i = a i + 1 , o i = ∣ l i − a i ∣ + ∣ r i − a i ∣
Δ = ∣ l i − a j ∣ + ∣ r i − a j ∣ + ∣ l j − a i ∣ + ∣ r j − a i ∣ − o i − o j \Delta = |l_i - a_j| + |r_i - a_j| + |l_j - a_i| + |r_j - a_i| - o_i - o_j
Δ = ∣ l i − a j ∣ + ∣ r i − a j ∣ + ∣ l j − a i ∣ + ∣ r j − a i ∣ − o i − o j
考虑枚举绝对值的符号，有
Δ = max s 1 , s 2 , s 3 , s 4 ∈ { − 1 , 1 } [ s 1 ( l i − a j ) + s 2 ( r i − a j ) + s 3 ( l j − a i ) + s 4 ( r j − a i ) − o i − o j ] \Delta = \max_{s_1, s_2, s_3, s_4 \in \{-1, 1\}} [s_1(l_i - a_j) + s_2(r_i - a_j) + s_3(l_j - a_i) + s_4(r_j - a_i) - o_i - o_j]
Δ = s 1 , s 2 , s 3 , s 4 ∈ { − 1 , 1 } max [ s 1 ( l i − a j ) + s 2 ( r i − a j ) + s 3 ( l j − a i ) + s 4 ( r j − a i ) − o i − o j ]
分离 i i i j j j
Δ = max s 1 , s 2 , s 3 , s 4 ∈ { − 1 , 1 } [ ( s 1 l i + s 2 r i − s 3 a i − s 4 a i − o i ) + ( s 3 l j + s 4 r j − s 1 a j − s 2 a j − o j ) ] \Delta = \max_{s_1, s_2, s_3, s_4 \in \{-1, 1\}} [(s_1 l_i + s_2 r_i - s_3 a_i - s_4 a_i - o_i) + (s_3 l_j + s_4 r_j - s_1 a_j - s_2 a_j - o_j)]
Δ = s 1 , s 2 , s 3 , s 4 ∈ { − 1 , 1 } max [( s 1 l i + s 2 r i − s 3 a i − s 4 a i − o i ) + ( s 3 l j + s 4 r j − s 1 a j − s 2 a j − o j )]
先枚举 i i i Δ \Delta Δ
Δ m a x = max 1 < j < i − 1 { max s 1 , s 2 , s 3 , s 4 ∈ { − 1 , 1 } [ ( s 1 l i + s 2 r i − s 3 a i − s 4 a i − o i ) + ( s 3 l j + s 4 r j − s 1 a j − s 2 a j − o j ) ] } = max s 1 , s 2 , s 3 , s 4 ∈ { − 1 , 1 } { max 1 < j < i − 1 [ ( s 1 l i + s 2 r i − s 3 a i − s 4 a i − o i ) + ( s 3 l j + s 4 r j − s 1 a j − s 2 a j − o j ) ] } = max s 1 , s 2 , s 3 , s 4 ∈ { − 1 , 1 } [ ( s 1 l i + s 2 r i − s 3 a i − s 4 a i − o i ) + max 1 < j < i − 1 ( s 3 l j + s 4 r j − s 1 a j − s 2 a j − o j ) ] \begin{aligned}
\Delta_{\mathrm{max}}
&= \max_{1 < j < i - 1} \{\max_{s_1, s_2, s_3, s_4 \in \{-1, 1\}} [(s_1 l_i + s_2 r_i - s_3 a_i - s_4 a_i - o_i) + (s_3 l_j + s_4 r_j - s_1 a_j - s_2 a_j - o_j)]\} \\
&= \max_{s_1, s_2, s_3, s_4 \in \{-1, 1\}} \{\max_{1 < j < i - 1} [(s_1 l_i + s_2 r_i - s_3 a_i - s_4 a_i - o_i) + (s_3 l_j + s_4 r_j - s_1 a_j - s_2 a_j - o_j)]\} \\
&= \max_{s_1, s_2, s_3, s_4 \in \{-1, 1\}} [(s_1 l_i + s_2 r_i - s_3 a_i - s_4 a_i - o_i) + \max_{1 < j < i - 1} (s_3 l_j + s_4 r_j - s_1 a_j - s_2 a_j - o_j)]
\end{aligned}
Δ max = 1 < j < i − 1 max { s 1 , s 2 , s 3 , s 4 ∈ { − 1 , 1 } max [( s 1 l i + s 2 r i − s 3 a i − s 4 a i − o i ) + ( s 3 l j + s 4 r j − s 1 a j − s 2 a j − o j )]} = s 1 , s 2 , s 3 , s 4 ∈ { − 1 , 1 } max { 1 < j < i − 1 max [( s 1 l i + s 2 r i − s 3 a i − s 4 a i − o i ) + ( s 3 l j + s 4 r j − s 1 a j − s 2 a j − o j )]} = s 1 , s 2 , s 3 , s 4 ∈ { − 1 , 1 } max [( s 1 l i + s 2 r i − s 3 a i − s 4 a i − o i ) + 1 < j < i − 1 max ( s 3 l j + s 4 r j − s 1 a j − s 2 a j − o j )]
枚举 s 1 , s 2 , s 3 , s 4 s_1, s_2, s_3, s_4 s 1 , s 2 , s 3 , s 4
我操我真想不到这个．
考察如何确定一个点 u u u u u u 1 1 1 u u u a n c u \mathrm{anc}_u anc u arg max v ∈ a n c u d e p v \argmax_{v \in \mathrm{anc}_u} \mathrm{dep}_v arg max v ∈ anc u dep v p u p_u p u w w w u ∈ a n c w u \in \mathrm{anc}_w u ∈ anc w x ∈ a n c w , x ∉ a n c u , d e p p u < d e p x < d e p u x \in \mathrm{anc}_w, x \not \in \mathrm{anc}_u, \mathrm{dep}_{p_u} < \mathrm{dep}_x < \mathrm{dep}_u x ∈ anc w , x ∈ anc u , dep p u < dep x < dep u u u u x x x w w w
这启发我们按照深度降序确定节点在新树中的父亲．对于叶子节点 u u u a n c u \mathrm{anc}_u anc u v v v u u u v v v a n c u \mathrm{anc}_u anc u v v v a n c v \mathrm{anc}_v anc v
若存在局面满足条件，显然在所有局面中中奖的次数是一定的，这确定了每个局面的概率，我们只需要计算局面数．
记 n + k c = m n + kc = m n + k c = m k k k k k k 0 0 0 − 1 -1 − 1 c − 1 c - 1 c − 1 m m m k k k c − 1 c - 1 c − 1 m − k m - k m − k − 1 -1 − 1 − n -n − n
对这样的序列计数，这在形式上像一个 Raney 引理 能够解决的问题，考虑构造双射使得其变成引理能处理的形式．由于序列的和为 − n -n − n − n -n − n 0 0 0 n n n 0 0 0 k k k 1 − c 1 - c 1 − c m − k m - k m − k 1 1 1 n n n n m ( m k ) \frac{n}{m} \binom{m}{k} m n ( k m )
令 t t t f u f_u f u u u u d u d_u d u u u u i n u \mathrm{in}_u in u u u u s s s t t t 1 1 1 0 0 0
设 U u U_u U u u → f u u \rightarrow f_u u → f u D u D_u D u f u → u f_u \rightarrow u f u → u U u = D u + i n u U_u = D_u + \mathrm{in}_u U u = D u + in u v v v u u u
U u = 1 d u − 1 ∑ v U v + [ u = s ] d u D v = 1 d u − 1 ( D u + ∑ v ′ ≠ v U v ′ ) + [ u = s ] d u \begin{align}
U_u &= \frac{1}{d_u - 1} \sum_v U_v + \frac{[u = s]}{d_u} \\
D_v &= \frac{1}{d_u - 1} \left(D_u + \sum_{v^\prime \not= v} U_{v^\prime}\right) + \frac{[u = s]}{d_u}
\end{align}
U u D v = d u − 1 1 v ∑ U v + d u [ u = s ] = d u − 1 1 D u + v ′ = v ∑ U v ′ + d u [ u = s ]
由 ( 1 ) (1) ( 1 )
∑ v U v = ( d u − 1 ) U u − d u − 1 d u [ u = s ] \sum_v U_v = (d_u - 1) U_u - \frac{d_u - 1}{d_u} [u = s]
v ∑ U v = ( d u − 1 ) U u − d u d u − 1 [ u = s ]
代入 ( 2 ) (2) ( 2 )
D v = 1 d u − 1 ( D u − U v + ∑ v ′ U v ′ ) + [ u = s ] d u = 1 d u − 1 ( D u − U v + ( d u − 1 ) U u − d u − 1 d u [ u = s ] ) + [ u = s ] d u D v + 1 d u − 1 U v = 1 d u − 1 D u + U u − [ u = s ] d u + [ u = s ] d u d u d u − 1 D v = 1 d u − 1 D u + U u − 1 d u − 1 i n v D v = 1 d u ( D u + ( d u − 1 ) U u − i n v ) \begin{aligned}
D_v
&= \frac{1}{d_u - 1} \left(D_u - U_v + \sum_{v^\prime} U_{v^\prime}\right) + \frac{[u = s]}{d_u} \\
&= \frac{1}{d_u - 1} \left(D_u - U_v + (d_u - 1) U_u - \frac{d_u - 1}{d_u} [u = s]\right) + \frac{[u = s]}{d_u} \\
D_v + \frac{1}{d_u - 1}U_v &= \frac{1}{d_u - 1} D_u + U_u - \frac{[u = s]}{d_u} + \frac{[u = s]}{d_u} \\
\frac{d_u}{d_u - 1}D_v &= \frac{1}{d_u - 1} D_u + U_u - \frac{1}{d_u - 1} \mathrm{in}_v \\
D_v &= \frac{1}{d_u} \left(D_u + (d_u - 1) U_u - \mathrm{in}_v\right)
\end{aligned}
D v D v + d u − 1 1 U v d u − 1 d u D v D v = d u − 1 1 ( D u − U v + v ′ ∑ U v ′ ) + d u [ u = s ] = d u − 1 1 ( D u − U v + ( d u − 1 ) U u − d u d u − 1 [ u = s ] ) + d u [ u = s ] = d u − 1 1 D u + U u − d u [ u = s ] + d u [ u = s ] = d u − 1 1 D u + U u − d u − 1 1 in v = d u 1 ( D u + ( d u − 1 ) U u − in v )
又有 U v = D v + i n v U_v = D_v + \mathrm{in}_v U v = D v + in v t t t r r r U r = i n r U_r = \mathrm{in}_r U r = in r ∑ U u + D u \sum U_u + D_u ∑ U u + D u
设 f S f_S f S S S S S S S p p p T i T_i T i i i i
∑ i = 1 n [ T i ∩ S = ∅ ] d i , p = ∑ T i ⊂ S ‾ d i , p \sum_{i = 1}^n [T_i \cap S = \varnothing] d_{i, p} = \sum_{T_i \subset \overline{S}} d_{i, p}
i = 1 ∑ n [ T i ∩ S = ∅ ] d i , p = T i ⊂ S ∑ d i , p
对每个测试点 p p p S S S O ( m 2 2 m ) O(m^2 2^m) O ( m 2 2 m )
考虑不修改怎么做，容易发现答案的分母肯定只由 1 1 1 d i s u , v \mathrm{dis}_{u, v} dis u , v
由于修改只会把边改小，设修改的边是 ( x , y , w ) (x, y, w) ( x , y , w ) u → v u \rightarrow v u → v min { d i s u , v , d i s u , x + w + d i s y , v } \min\{\mathrm{dis}_{u, v}, \mathrm{dis}_{u, x} + w + \mathrm{dis}_{y, v}\} min { dis u , v , dis u , x + w + dis y , v }
考虑不修改的时候何时字典序最小，这其实是经典结论：我们定义字符串 a a a b b b a + b a + b a + b b + a b + a b + a
对于任意确定的拼接方式和修改次数 k k k k k k a \texttt{a} a a \texttt{a} a a \texttt{a} a a \texttt{a} a
若我们已经确认了那些字符串被修改，剩余的字符串只能按上文定义的顺序拼接作为后缀．故我们先把输入的字符串按上文定义的顺序排序，顺序考虑当前字符串以何种状态进入答案．设 f i , j , 0 / 1 = ( a , s ) f_{i, j, 0 / 1} = (a, s) f i , j , 0/1 = ( a , s ) i i i j j j a \texttt{a} a a a a s s s
考虑如何进行转移．先考虑当前字符串以第二种状态出现在答案中的情况．设当前字符串为 s s s a \texttt{a} a k k k c o s t = ∑ p ≤ k [ s i , p ≠ a ] \mathrm{cost} = \sum_{p \le k} [s_{i, p} \not= \texttt{a}] cost = ∑ p ≤ k [ s i , p = a ] f i − 1 , j , 0 = ( a , t ) f_{i - 1, j, 0} = (a, t) f i − 1 , j , 0 = ( a , t ) substr ( s , k + 1 ) \operatorname{substr}(s, k + 1) substr ( s , k + 1 ) s s s k + 1 k + 1 k + 1
f i , j + c o s t , 1 ← ( a + k , substr ( s , k + 1 ) + t ) f_{i, j + \mathrm{cost}, 1} \leftarrow (a + k, \operatorname{substr}(s, k + 1) + t)
f i , j + cost , 1 ← ( a + k , substr ( s , k + 1 ) + t )
再考虑作为第一类状态时．设当前字符串为 s s s c o s t = ∑ p [ s i , p ≠ a ] \mathrm{cost} = \sum_p [s_{i, p} \not= \texttt{a}] cost = ∑ p [ s i , p = a ] f i − 1 , j , k = ( a , t ) f_{i - 1, j, k} = (a, t) f i − 1 , j , k = ( a , t )
f i , j + c o s t , k ← ( a + ∣ s ∣ , t ) f_{i, j + \mathrm{cost}, k} \leftarrow (a + |s|, t)
f i , j + cost , k ← ( a + ∣ s ∣ , t )
最后考虑作为第三种状态，后缀的字典序最小性由排序保证．记 f i − 1 , j , k = ( a , t ) f_{i - 1, j, k} = (a, t) f i − 1 , j , k = ( a , t )
f i , j , k ← ( a , s + t ) f_{i, j, k} \leftarrow (a, s + t)
f i , j , k ← ( a , s + t )
考察任意操作序列的“搜索树”．这里的搜索树这样构造：压栈操作在当前节点下新挂一个儿子，弹栈操作将当前节点修改成当前节点的父亲，和常规意义上的搜索树的不同之处在于允许点重复出现．
不难发现任意一个操作序列唯一对应一个“搜索树”，而该操作序列的答案就是搜索树的最大深度．题目要求“按顺序访问所有所有特殊点”，说的其实是题目定义的访问记录构成的序列存在子序列是 x x x x i x_i x i a c c e s s ( x i ) \mathrm{access}(x_i) access ( x i ) x i x_i x i x i + 1 x_{i + 1} x i + 1 a c c e s s ( x i ) \mathrm{access}(x_i) access ( x i ) a c c e s s ( x i + 1 ) \mathrm{access}(x_{i + 1}) access ( x i + 1 ) a c c e s s ( x i ) \mathrm{access}(x_i) access ( x i ) a c c e s s ( x i + 1 ) \mathrm{access}(x_{i + 1}) access ( x i + 1 ) x i x_i x i x i + 1 x_{i + 1} x i + 1 a c c e s s ( x i ) \mathrm{access}(x_i) access ( x i ) a c c e s s ( x i + 1 ) \mathrm{access}(x_{i + 1}) access ( x i + 1 ) a c c e s s ( x k ) \mathrm{access}(x_k) access ( x k ) k k k
设 f u , l , r f_{u, l, r} f u , l , r u u u x l ∼ x r x_l \sim x_r x l ∼ x r u u u x l x_l x l x r x_r x r u u u r = L r = L r = L x r x_r x r u u u
先考虑 u u u x k x_k x k x k + 1 x_{k + 1} x k + 1 u u u x k x_k x k x k + 1 x_{k + 1} x k + 1
f u , l , r ← max { f u , l , k , f u , k + 1 , r } f_{u, l, r} \leftarrow \max\{f_{u, l, k}, f_{u, k + 1, r}\}
f u , l , r ← max { f u , l , k , f u , k + 1 , r }
再考虑在当前联通块的根上挂一条祖先链，或者说连续执行弹栈操作导致的转移．假设从 f v , l , r f_{v, l, r} f v , l , r f u , l , r f_{u, l, r} f u , l , r u u u x l x_l x l v v v r ≠ L r \not= L r = L x r x_r x r u u u v v v
f u , l , r ← f v , l , r + d i s u , v f_{u, l, r} \leftarrow f_{v, l, r} + \mathrm{dis}_{u, v}
f u , l , r ← f v , l , r + dis u , v
其中 d i s u , v \mathrm{dis}_{u, v} dis u , v u u u v v v
由于我们计算的都是边深度，最终答案为 f x 1 , 2 , L + 1 f_{x_1, 2, L} + 1 f x 1 , 2 , L + 1 x x x 1 1 1
考察一条边 ( u , v ) (u, v) ( u , v ) u u u v v v u u u ( u , v ) (u, v) ( u , v ) u u u u u u u u u v v v u u u v v v
所以设 f u , i f_{u, i} f u , i u u u u u u j j j u u u i i i u u u i − 1 i - 1 i − 1 u u u v v v s v s_v s v ∑ v s v = i − 1 \sum_v s_v = i - 1 ∑ v s v = i − 1 v v v k k k v v v k k k ∑ d ≥ k f v , d \sum_{d \ge k} f_{v, d} ∑ d ≥ k f v , d s u f v , k \mathrm{suf}_{v, k} suf v , k
f u , i = ∑ s ( i − 1 s 1 , s 2 , ⋯ ) ∏ v s u f v , s v f_{u, i} = \sum_s \binom{i - 1}{s_1, s_2, \cdots} \prod_v \mathrm{suf}_{v, s_v}
f u , i = s ∑ ( s 1 , s 2 , ⋯ i − 1 ) v ∏ suf v , s v
预处理后缀和后树形背包合并即可．
按 p i p_i p i i i i i i i i i i p i p_i p i
首先发现若我们决定操作某位，我们可以将序列中所有元素的该位任意赋值．从高到低按位考虑答案，考虑何时该位必须被操作．我们钦定该位不操作，并允许操作比其低的所有位，如果仍无法得到不降序列，则该位是必须的．
问题转化为给定允许操作的位集，判定能否得到不降序列．顺序考虑序列中的元素，尝试计算当前能够得到最小的前缀最大值（即前缀中的最后一个元素），先将允许操作的位集全部置 1 1 1 0 0 0