据说是llsw出的题
我是没上200的丝薄
记 f u , K f_{u,K} fu,K表示从 u u u出发，走 K K K次后价值和的最大值。
假设有 m m m个儿子，那么 f u , K = ∑ v f v , K / m + ∑ v ′ f v ′ , K / m + 1 f_{u,K}=\sum_v f_{v,K/m}+\sum_{v'}f_{v',K/m+1} fu,K=∑vfv,K/m+∑v′fv′,K/m+1 。
直接排序即可。应该可以感觉到状态数是线性的。
复杂度 O ( n log n ) O(n\log n) O(nlogn)。
#include原题为「Gym102331C」Counting Cactus
姑且称之为仙人掌计数。
令 f ( u , S ) f(u,S) f(u,S)表示 u u u号节点为根，节点集合为 S S S的方案数。
令 g ( u , S ) g(u,S) g(u,S)表示 u u u号节点为根，且 u u u恰好只在一个环上，节点集合为 S S S的方案数。
令 d p ( u , v , S ) dp(u,v,S) dp(u,v,S)为钦定一个当前环的开头是 u u u，环尾扩展到了 v v v，节点集合为 S S S的方案数。
转移方程为：
1.1
1.1
1.1 设
v
v
v为编号最小的节点，并且
v
∈
T
v\in T
v∈T，
(
f
v
,
T
+
g
u
,
T
+
{
u
}
)
×
f
u
,
S
−
T
→
f
u
,
S
(f_{v,T}+g_{u,T+\{u\}})\times f_{u,S-T}\to f_{u,S}
(fv,T+gu,T+{u})×fu,S−T→fu,S
1.2
1.2
1.2 若
u
u
u在环上，且环的终点为
v
v
v，
(
u
,
x
)
∈
E
(u,x)\in E
(u,x)∈E，
d
p
x
,
v
,
S
−
{
u
}
→
f
u
,
S
,
g
u
,
S
dp_{x,v,S-\{u\}}\to f_{u,S},g_{u,S}
dpx,v,S−{u}→fu,S,gu,S
1.3
1.3
1.3 对于
u
→
v
u\to v
u→v的链，在
u
u
u上挂一个仙人掌，满足
(
u
,
x
)
∈
E
(u,x)\in E
(u,x)∈E，
u
∈
T
u\in T
u∈T，
x
,
v
∉
T
x,v\notin T
x,v∈/T，
d
p
x
,
v
,
S
−
T
×
f
u
,
T
→
d
p
u
,
v
,
S
dp_{x,v,S-T}\times f_{u,T}\to dp_{u,v,S}
dpx,v,S−T×fu,T→dpu,v,S
注意环有顺逆时针两种情况，所以要 / 2 /2 /2。
复杂度 O ( 3 n n 3 ) O(3^nn^3) O(3nn3)。上界很松。通过固定转移系数 f u , T f_{u,T} fu,T可以优化至 O ( 3 n n 2 ) O(3^nn^2) O(3nn2)。
有更好的方法，但是我不会。
#include神秘多项式。。。
应该可以看出来这是一个拟阵。
不妨将其转化为二分图匹配，使用 hall \text{hall} hall定理，只需关注右部点中的一段连续区间。问题转述为，对于任意 1 ≤ i ≤ j ≤ m 1\le i\le j\le m 1≤i≤j≤m， s r j − s l i − 1 ≥ j − i + 1 s_{r_j}-s_{l_i-1}\ge j-i+1 srj−sli−1≥j−i+1，其中 s i s_i si表示 a i a_i ai的前缀和。
不妨将话说明白些。分参易得 s r j − j ≥ s l i − 1 − i + 1 s_{r_j}-j\ge s_{l_i-1}-i+1 srj−j≥sli−1−i+1。
我们将其视作位置 i i i的排名 f i f_i fi, g i g_i gi。那么对于任意 j ≥ i j\ge i j≥i有 f j ≥ g i f_j\ge g_i fj≥gi。每次插入一个操作只会影响 i i i, j j j（相对位置），因此前面的排名不变，设插入位置为 k k k，只需判断 max i = 1 k g i \max_{i=1}^k g_i maxi=1kgi与 min i = k m f i \min_{i=k}^mf_i mini=kmfi的大小关系，因此用两颗线段树维护。
复杂度 O ( n log n ) O(n\log n) O(nlogn)。
#include