P4764
值域为 \([l,r]\) 的生成森林，也就是把值 \(\ge l\) 的边拿出来生成森林，其中边 \(\le r\) 的权值和。
我们现在要求所有 \(l\)，$\ge l $ 边的生成森林中边有哪些。
考虑从大往小加边，设当前加入第条边 \((u,v,w)\)。
因为这条边最小，所以这条边必选。若 \(u,v\) 不连通，那么直接连边。
若 \(u,v\) 联通，那么选 \(u\to v\) 路径上最大的边删去，这个直接 dfs 即可。
由于边的变化量是 \(O(1)\) 的，我们直接用主席树维护即可。
这种问题考虑生成树的性质，要排序。
P8352
设 \(f_{u,0/1}\) 表示求解独立集，\(u\) 选/不选的代价。
暴力的话把 \(f_{u,0},f_{u,1}\) 都作为状态，放进外层 dp 里，转移的话树上背包。
这样是 \(O(n^4)\) 的复杂度。我们没有考虑到 \(f_{u,0/1}\) 之间的联系。
更改定义，设 \(f_{u,0/1}\) 表示是否强制 \(u\) 不选的代价。
注意到 \(0\le f_{u,0}-f_{u,1}\le k\)，那么我们设计 \(dp_{u,w,c}\) 表示 \(f_{u,0}-f_{u,1}=c,f_{u,1}=w\).
转移就那样。\(O(n^2)\).
这种问题是 dp of dp.
P5300
考虑先拆位。AND 和 OR 同理，变成数有多少个子矩形满足里面没有 \(1/0\).
考虑对于每一列讨论。从下往上扫，维护一个单调栈，表示以当前点为左上角，右下角的取值。
这种问题是单调栈的应用。
P5283
做前缀和，加上 01Trie 可以查询以一个位置为结尾与前面位置的异或和第 \(k\) 大。
若每个位置都计算 \(k\) 大去更新，那么达到了 \(O(nk)\).
如果我们把所有的右端点都一起去计算呢？考虑可持久化 01trie.
在上面二分即可。
这种问题是 01trie 解决异或问题的典型。
CF1918E
首先我们可以通过 \(O(n)\) 次询问找到一个位置的值。
而每次花销这么大是因为 \(x\) 的位置变动很大，如果我们把值相近的放在一起呢？
考虑分治，我们每次确定一个数 \(mid\)，把大于、小于分开放，继续进行分治。
如果随机确定，那么应该也是 \(\log\) 层的，总共是 \(O(n\log n)\) 级别。
因为我们不知道 \(x\) 的值，但是可以知道相对大小，我们最后只需把他们赋给 \(1\sim n\) 即可。
这种问题需要想到按照值域分治。
CF1918F
首先把 \(k\) 设为 \(k+1\)，这样最后一定要回到根节点，操作同质化。
如果不适用 \(2\) 操作，每条边经过两次，代价是 \(2(n-1)\)，计算能节省多少费用。
如果我们用 \(2\) 操作，假设我们从 \(u\) 要到 \(v\)，本来要花费 \(d_u-d_v\) 的代价，现在只需 \(d_v-1\) 的代价。
节省了 \(d_u-2d_v+1\) 的代价。
对于 \(v\) 考虑，\(u\) 一定是 \(v\) 子树内深度最大的几个点，且 \(v\) 每个儿子子树只能用一次。
那我们只需要选出节省代价最多的 \(k+1\) 即可。
这种问题要想到贪心，以及要转化考虑对象。