11.28模拟赛D题解

一个奇妙的不等式操作：
(a_x+a_ygeq (a_x xor a_y)=f_x-f_y)
所以只有(a_x+a_ygeq f_x-f_y)的点才能贡献答案。
这个东西的意义是(a_xgeq 在)x(子树且不包含)x(,)y(子树的点)。
考场上猜了符合这个条件的点对只有(nlog_2max a_i)，结果真的猜对了。
要证明这个需要证明两个引理：
1.合法的候选(y)集可能在多个子树中，但是一定在一个子树的链中。
假设有两个点(x,y)不在一条直上/下的链上，则设他们的lca是(lc)。
显然(a_xgeq a_y+a_{lc})且(a_ygeq a_x+a_{lc})
(a_{lc})一定大于(0)所以矛盾。
2.一个子树候选点最多只有(log_2{max a_i})个。
构造一数列(b_x)表示(x)（(x)必须是候选集内节点）到父亲的链的(a)的和。
显然(a_xgeq b_{ff_x} ,b_{x}=b_{ff_x}+a_x)，(ff_x)表示它的祖先中，深度最大的候选点。
显然(b_x)每次至少会比(b_{ff_x})翻倍，证完。
所以符合这个条件的点对在最坏情况下只有(sum deg_i*log_2{max a_i}=nlog_2{max a_i})。
所以可以轻松的计算答案。
算法1：显然使用dfs序+线段树即可轻松的维护一个点往外的权值，然后在线段树上dfs统计答案，当区间最小值(>0)的时候break，但是没调出来。
算法2：注意到一个点在dfs的计算过程中（逆dfs遍历所有点），成为候选集的位置，肯定是一段连续的区间。
在考虑到它的点（祖先）肯定越高越不可能满足要求。
所以可以把当前点的候选集合并到祖先然后暴力计算。
实际上，在考场上我想到了算法2，但是以为时间复杂度是错的没写。