啊呜
C
傻逼出题人，不会枚举无根树，写了依托答辩。
发现最后的形状一定是个树，因为不是树的话，能构造一个从不是树到树的单射，所以最后肯定是个树，然后21个点的本质不同的树不超过 \(4\cdot 10^6\) 个，所以可以直接枚举、
我是先 \(10!\) 加树哈希枚举出所有大小为 \(10\) 以下的所有树，然后对于大小超过 \(10\) 的树，用重心定根之后每个子树的大小不超过 \(10\) ，枚举一下分配然后把每个儿子接上去就好，然后再跑一遍dp，就可以得到答案，取个最大值就好。
L
有\(n\)个点，要进行\(k\)次：选择\(i\in[1,n]\cap Z\)，连接\((i-1,i)\)。有\(m\)个条件奖励\((l_i,r_i,v_i)\)：如果\(l_i\)和\(r_i\)联通则可以得到\(v_i\)。对每个\(k\in [1,n]\cap Z\)求可获得的最大奖励值。\(n,m\le 1e4\)。
考虑一个简单dp，\(f_{i,j},g_{i,j}\)分别表示考虑\([0,i]\)的点，选了\(j\)条边，边\((i-1,i)\)选/没选的最大答案。转移：
\[ f_{i,j}=\max_{i'<i}\{g_{i',j-(i-i')}+w(i',i)\} \newline g_{i,j}=\max\{g_{i-1,j},f_{i-1,j}\} \]
发现如果令\(j'=j-(i-i')\)，则\(i-j=i'-j'\)，那么结合\(g\)的转移，可以考虑从小到大枚举\(i-j\)滚动dp。
如果滚动\(i-j\),那么\(g\)的转移好办，\(f\)的转移有些麻烦。考虑搞一个数据结构，直接求出最好的\(i'\)作为\(f\)的转移。观察枚举\(i-j\)之后，再一个个从小到大枚举\(i\)的时候会发生什么：当\(i\to i+1\)，发生了两个改变：首先\(g_{i,j}\)变成了新增的可用转移源；其次，那些以\(i+1\)为右端点的奖励需要被加到\(w\)里面去：\(w(i',i+1)=w(i',i)+\sum_{r=i+1}v\)。
考虑怎么维护\(\{g_{i',j-(i-i')}+w(i',i)\}\)。结合上面的改变，以\(i'\)为下标这个数据结构需要实现：
对某个前缀加上一个正数
在尾部append一个正数
查询整个序列的最大值
如果时限不紧，可以考虑线段树。考虑到这题时限很近，可以考虑用序列并查集维护单调栈。每个点的父亲是单调栈上罩住它的点，并查集块根就是单调栈上的点。那么前缀加的时候就是单调栈上删点，两个区间合并，append的时候要么加入一个新块，要么被全局最大值罩住。每个单调栈上的点维护它到下一个单调栈上的点的差值方便前缀加做合并，全局最大值点维护其自身的值方便查询答案。查询整个序列的最大值就是序列最后一个点所属块块根的值。
时间复杂度\(O(n^2\alpha(n))\)，空间可以通过滚动做到线性。