E. Eert Esiwtib Solution 由于值域很小，考虑对每个更新整棵树计算对应的询问。 设表示以为根的子树得到的三种答案分别是什么，容易发现i连的若干个子树的对答案的贡献互不影响，那么来看看如何转移： 如果当前点连到子节点的边是 对于答案，有，所以可以直接 对于答案，有，所以可以 对于答案，就麻烦些，考虑对所有位分成两部分，一部分是包含的，一部分是不包含的，那么不包含的部分显然可以用直接转移，包含的部分就需要考虑一下子树大小的奇偶，如果是奇数则对应位全是1，否则全是0，所以有 如果当前点连到子节点的边是 对于答案，有，所以有 对于答案，有，所以有 对于答案，，还是分...

G. Greater Integer, Better LCM 前言 题解有点看不懂，自己想了个比较直接的做法。 Solution 考虑和的因数是由哪些组成的，于是发现这两个数选到的最终要包含所有，所以直接考虑枚举其中一个数，那么另一个数能取的范围就是“至少包含当前数的补集的所有数”，换句话说，我们选定一个数后，这个数有哪些选满了已知，那么另一个数一定要把没选满的都选满，所以只要能预处理出“至少某几位选满时的最小值”就可以了。 这个预处理其实很简单，先直接dfs求出恰好某几位选满时的答案，然后直接SOSDP即可。 最终统计答案时的dfs和预处的dfs几乎完全一致。 中间特别注意一下选...

J. Defend Your Country 前言 思维题，主要是要猜结论证结论。 Solution 对于n是偶数的情况，显然不需要删边。 对于n是奇数的情况，删去非割点显然只用删一个，主要是考虑删掉割点的情况。 假设删除了偶数个割点使得答案最优，由于剩下的联通块必然都是偶数个点（否则继续删奇数联通块更优），推出总点数是偶数，与“n是奇数”矛盾，所以如果删掉割点最优，我们一定会删掉偶数个割点。 显然如果删割点最优，非割点一定不会被删，否则的话只删一个非割点更优。 现在来证明一下，删除的割点个数一定是1，即不可能删除3个或以上的割点： 删除多个割点后，产生的联通块中如果还有奇数且大于1的联通块就...

D. Rebuild Tree 前置芝士：prufer序列 prufer序列是将n个点的标号的无根树对应到长度为n-2，每个位置值域为[1,n]的序列。 prufer序列的构造方法是每次将树中编号最小的树叶删除，将树叶连接的点加入prufer序列。 树上点x的度数=prufer序列中x出现的次数+1。 Solution 题意相当于砍掉k条边再加上k条边，构成一棵树的方案数。 首先来考虑当砍掉的k条边确定时，此时树被分成了k+1棵树，我们设每棵树的节点个数是 我们把这些树抽象成点，因为最终就是要在这k+1棵树之间连k条边使得最终成一棵树；考虑当连边的方案已经确定时 此时这k+1个...

Solution 这个题的转换还是有难度的。 我们观察一下，对于可以包含其他区间的大区间，要使得答案最优无非就是两种分组方式：单独一组或者与被包含的区间一组。因为根据题意，如果有多个区间，添加区间实际上是添加限制，会使得答案变小，于是能包含其他区间的这些区间实际上是可以独立出来的，我们把这部分区间去掉，观察剩下的区间有什么性质。 将剩下的这部分区间按左右端点双关键字排序，那么从左到右区间的左端点是单调不降的，又由于前面将大区间都去掉了，所以实际上右端点也是单调不降的，这个性质就非常好了，如果我们选择了某两个区间​​​分到一组，那么这一组的贡献显然是​​，对于中间的任意一个区间​​，由前面的分析...