T1 彩虹生成树(coltree)
首先，一个等价条件是每种颜色选一条边，不形成环。
首先是只有一条边的颜色肯定可以先选上，然后把点缩起来，缩完再给其他颜色的边去重。那如果所有颜色都有>1条边呢？缩完点还可能会有重边。
大概感觉一下，复杂度肯定带一个 \(2^k\)，相当与枚举颜色集合。等价条件是对于任意颜色集合 \(S\)，只保留颜色在 \(S\) 中的边，\(n -\) 连通块个数 \(\ge|S|\)。咋证啊。
算了我猜这是对的。然后就是 \(2^k\) 枚举，然后上线段树分治维护连通性了。\(O(2^kn \log n)\) 有 70 吗。怎么只有 35。
草我怎么写成枚举集合后加边了。直接写...90？我写成可撤销并查集试试。还是90。卡一会儿常，过了。
哦原来复杂度是 \(O(2^kn\log k)\)，我说怎么这么快。
什么叫正解是拟阵交 \(O(nk^3)\)？
T2 你终将驾驭自己的心(heart)
何意味？不想给部分分可以不给。
T3 排列游戏(perm)
只有 \(1\) 的祖先的贡献不为 \(1\)，因此考虑令 \(dp_{u,i}\) 表示 \(u\) 的子树中 \(mex=i\) 的所有方案权值之和，且要求 \(i \ge 2\)。对于转移，若从 \(dp_{v,j}\) 转移到 \(dp_{u,i}(i\ge j)\)，则唯一的限制是 \(j\) 不能填到 \(v\) 的子树内，剩下 \(i-j-1\) 个随便填。因此特判掉 \(dp_{v,i}\to dp_{u,i}\) 的转移，剩下的拆拆贡献前缀和优化就行了。
复杂度是树形背包的 \(O(n^2)\)。