2022/10/24 做题记录

QwQ

http://47.92.197.167:5283/contest/268/problem/3

发现一组匹配的答案是两棵树上深度相同的祖先对数量， $\sum_{dep_{1,i}=dep_{2,j}}\sum_{(u,v)} [u,v \in T_{1,i}][u,v \in T_{2,j}]$，这个式子最大值能取到 $\sum_{dep_{1,i}=dep_{2,j}}\lfloor\frac{|T_{1,i} \cap T_{2,j}|}{2}\rfloor$，构造方式就是深度从大到小一层层考虑，每层尽量匹配，最多一个匹配不上，而且也不可能出现冲突。

考虑如何动态维护这个式子，我们每次会给两条到根的链上加 1，这样会有 $O(n)$ 个点对权值产生变化，但我们给树重链剖分之后，这 $O(n)$ 个点对能被划分到 $O(\log n)$ 个重链交之中，不难发现所有每个点对恰好会被划分到一个重链交之中，至于对于一个重链交里的若干个点对，我们的操作就是给它的一个前缀的权值加 1，查询每一个数除二下取整的和，显然可以动态开点线段树维护每个区间奇数偶数的个数，但空间不够，于是考虑平衡树，每个点维护一个权值相等的端，需要 split 的时候再把一个点拆开，这样空间还是平衡树的 $O(n)$，于是时间 $O(n \log^2n)$，空间 $O(n \log n)$

会是（willbe）

首先我们询问所有的 $(i,i+1)$，这样如果 bfs 序上相邻的两个点距离是奇数那么说明在同一层，偶数说明第二个点在新的一层，这样我们可以顺便处理出所有点的深度。

还原树的结构是比较难的，但我们只需要所有点的答案和，首先不难发现将两个父亲相同的点的子树（除了根）交换是不影响答案的，如果两个点不在同一层，直接新开一层，把它置为第一个点（相当于把它原来的位置交换到第一个），并更新每一层第一个点的答案即可，如果在同一层，我们通过 $dis(i,i+1)$ 可以知道它们的 lca 是什么，但并不知道是哪个儿子，可以发现直接将它接到第一个儿子上就是对的（因为这样相当于把本来要放的那个子树通过上面的方式交换到第一个），于是我们维护若干个指针表示它到根的链经过了每一层的第几个节点，之后就将 lca 以下的每一个指针加一即可，同时更新这些点的答案，这样是 $O(n^2)$，而我们也能发现我们一定是给更新的那些点答案增加一，于是其实在每一步更新的点的数量和就是答案，可以 $O(n)$ 做。