设 f_i 为跳到 i 所需的最小代价，则 f_i=\min_{j=i-k}^{i-1}f_j+[d_i\ge d_j]，考虑用单调队列，需要判断两个点的优劣。发现 f_x<f_y 时 x 一定更优，若 f_x=f_y， 则 d_x>d_y 时 x 一定更优。因为每次的代价仅为 1，所以这样是对的。把 (f_i,d_i,i) 放入单调队列，用队首更新即可。
树形 DP
E - Centroids
先找出重心，原重心一定合法。以重心 g 为根计算每个点的子树大小。若 {siz}_x=\frac n2，可以直接把这颗子树拆下来，把剩余的 \frac n2 接到指定的根上，保证会成为重心。所以 x 子树内的点均合法。
对于其他点，断开自己子树显然是不合法的，那么只能断开 g 其他子树中 siz 最大的 k，且直接接到 x 上。那么 siz_x,siz_k 均小于 \frac n2，只要 n-siz_x-siz_j\le\frac n2 即合法。预处理一下 g 子树的前缀后缀 siz 最大值，求子树 m 时用前缀和后缀的最大值作为 siz_k 即可。
G - 树上染色
考虑把贡献拆到边上，并在从子树合并到父节点时考虑进去。所以若子树 v 中有 j 个黑点，贡献的次数为 S=j(k-j)+(siz_v-j)(n-siz_v-(k-j))。合并入父节点时，转移为 f_{u,i}=\min_{j=0}^{{siz}_v} f_{u,i-j}+f_{v,j}+Sw。
注意外层 i 逆序枚举以保证 01 背包的性质，内层枚举顺序无所谓，但是一定要在开始时处理 j=0，也就是直接把这个子树中纯白的情况考虑进去了，否则在后面会直接加上 Sw 导致算重。
C - 小 N 的独立集
考虑最朴素的算法，2^n 枚举每个点的取值，然后直接 O(n) 跑树上最大独立集，设 f_{u,0/1} 表示 u 不选/选时，u 子树内的最大收益。接着考虑 DP 套 DP，把 f 设入状态，设 g_{u,v_0,v_1} 为以 u 为根的子树中 u 不选时最大值为 v_0，选时最大值为 v_1 的方案数，更新时用 g_{v,p,q} 更新 g_{u,i+\max(p,q),j+p}=g_{u,i+\max(p,q),j+p}+g_{v,p,q}\times g_{u,i,j}。
首先注意到确定分割位置后，无论分割顺序怎样，最终的结果相同，因为每个元素都会与所有与其所在部分不同的元素相乘。所以设 f_{i,j} 表示考虑到前 i 个元素，分了 j 块的最大得分，有 f_{i,j}=\max_{k=j-1}^{i-1}f_{k,j-1}+s_k(s_i-s_k)，其中 s 是 a 的前缀和数组。