格雷码
模拟即可。需要注意的是要开 unsigned long long。
括号树
先考虑一条链的情况，即给出一个括号序列，求出每个前缀的所有子段中有多少个合法括号序列。
假设我们在计算 $[1,i]$ 的答案，那么它显然等于 $[1,i-1]$ 的答案加上强制选 $i$ 的答案。
维护一个栈表示所有未被匹配的左括号，再求出一个 $len_i$ 表示存在某个位置 $p$，满足 $[p,i]$ 能够拆成 $len_i$ 段，且每段都是合法括号序列，在此基础上最大的 $len_i$。
假设 $i$ 是右括号，记 $pre_i$ 表示与 $i$ 匹配的左括号的位置，显然有 $len_i=len_{pre_i-1}+1$。然后强制选 $i$ 的答案就是 $len_i$。
然后把这个东西搬到树上即可，具体的一些细节可以看代码。
树上的数
咕咕咕
Emiya 家今天的饭
首先可以把烹饪方法看做行，主要食材看做列。
考虑容斥掉第三个限制。注意到不满足第三个限制的列至多只有一个，因此我们仅需要计算出无第三个限制时的方案数以及某一列超过 $\left\lfloor\frac{k}{2}\right\rfloor$ 时的方案数。
首先计算第一部分（无第三个限制时的方案数）。设 $f_{i,j}$ 表示前 $i$ 行选了 $j$ 个的方案数，$sum_i$ 表示第 $i$ 行的和，容易得到
$$
f_{i,j}=f_{i-1,j}+sum_i\times f_{i-1,j-1}
$$
然后计算第二部分。假设钦定了第 $c$ 列不满足限制。设 $g_{i,j}$ 表示前 $i$ 行，第 $c$ 列选的数比其它列选的数多了 $j$ 的方案数，容易得到
$$
g_{i,j}=g_{i-1,j}+a_{i,c}\times g_{i-1,j-1}+(sum_i-a_{i,c})\times g_{i-1,j+1}
$$
然后算答案就很简单了。
划分
容易发现段数越多答案会越小，证明略。
设 $sum_i$ 为前缀和，$pre_i$ 表示最大的满足 $sum_i-sum_k\geq sum_k-sum_{pre_k}$ 的 $k$。
那么每个 $i$ 都会从 $pre_i$ 转移过来。
考虑如何快速求出 $pre_i$。我们把这个式子移一下项
$$
sum_i\geq 2sum_k-sum_{pre_k}
$$
用单调队列维护即可。
实现时开高精数组可能会爆空间，事实上直接最后利用 $pre$ 求出方案并算出答案即可。当然也可以直接 __int128
树的重心
考虑到一个事实：如果 $u$ 不是重心，则重心在 $u$ 的重儿子所在的子树中。
那么就有一种找重心的方法：不断跳重儿子直到不可能为重心，此时最后一个可能为重心的点和它的父亲都可能是重心，检查一下即可。
这样子是 $\mathcal{O}(n)$ 的，使用倍增即可优化至 $\mathcal{O}(\log n)$。
现在考虑如何求出删去一条边后得到的两棵树的重心。假设删去了 $(u,v)$ 且 $u$ 是 $v$ 的父亲。
考虑一下我们需要什么东西才能求出重心。我们需要一个重儿子的倍增数组，和一个记录子树大小的数组。
那么 $v$ 子树中这些东西和原树中相同，可以直接求；而 $u$ 子树中的这些东西用换根法求出即可。
4 条评论
催更D1T3
还有D2T1有锅
fixed