【习题选讲】树的进阶
难度递增！
CF1305D
n / 2 次询问，想到每次删至少两个节点。最暴力的思路是选任意两个节点，将 lca 为根的两个节点所在的子树删掉，但是这会被一条链的情况卡成询问 n 次。考虑选任意两个叶子，若 lca 等于其中之一那么那个叶子就是根，否则删除两个叶子。
CF1210C
询问每条链的 gcd 之和。考虑 gcd 一个很重要的性质：长度为 n 的区间所有子区间的 gcd 不会超过 logn 个。log 级别，开 vector 或者 map 存每个节点为下端点的链gcd，每次更新只有 logn 复杂度。
CF980E
考虑到 2^i 是个很特殊的东西，必然贪心的选 i 大的节点。按 i 从大到小排序，i 节点保证被选的前提是 i 到根的所有节点都保留，暴力判保留节点后是否超过 n - K 会 TLE，可以用 dfs 序上树状数组。做标记暴力跳就好了，反正是 O(n).
CF1098C
考虑 K（最大分支）满足二分性质，先二分出最终答案 ans，判能否构成树的条件是：一条链形式的子树和 >= S, K 叉树形式的子树和 <= S。构造也很容易，我的方法是将一条链的末尾节点不断挂上来，填一棵 K 叉树。
CF1149C
有意思的题，考虑直径的括号序列，必然是 )))())))…(((((()(((( 这样 ‘)))))’ + 匹配括号 + ‘(((((‘ 的形式。经典套路，将 ( 设为 1，) 设为 -1，答案就是相邻的两段序列之差最大值，可以用线段树维护（各种细节啊啊啊。。
CF1083C
有意思的题+1，询问每条链最大的 mex。神仙做法。首先，能线段树维护的信息都具有可合并性。容易想到二分 mex，判能否构成链。线段树 [l, r] 节点表示 权值为 l ~ r 的节点能否构成链，合并时枚举端点用 lca 判点是否在路径上即可。最后外面那个二分也可以省掉，直接在线段树上“二分”，统计答案。
AGC023F
神仙题++
先考虑前置问题：两个 01 序列相接，逆序对尽量小
设它们 01 个数分别为 sx0, sx1, sy0, sy1, x < y
显然 sx1 sy0 <= sx0 sy1 时不必交换两者。
变形：sx1 / sx0 <= sy1 / sy0.
考虑此题，初始时将点看作连通块，取出目前没有被选且 s1 / s0 最小的连通块（堆维护）
若它的父亲已经被选，就选了它；否则容易证明它一定会在它的根的父亲被选后立刻被选，就将它和根的父亲所在连通块合并，得到新的连通块
类似的还有 POJ2054-Color a Tree，贪心的每次将最大的点和它父亲合并
CF1168D
充要条件是所有叶子的深度相同，设为 mxdep, 设 lenx = mxdep - depx
且对于任何节点 x，sum{f(x, c)} <= lenx，其中 f(x, c) 表示任何一条 x 到其子树中叶子的链上 c 出现次数的最大值
证必要性：显然 证充分性：据说用归纳法证明
怎么处理修改？总不能每次暴力往上跳修改 f(x, c) 吧。
注意到当节点只有一个孩子时不需要判上面那个东西，相当于可以忽视
因此想到将父亲只有自己一个孩子的节点向上压缩，修改的复杂度就是深度
而满足每一层的节点个数都严格大于上一层（不然就压缩了），深度只有 sqrt(n)
总复杂度就是 O(Qsqrt(n)), 非常的喵！