2022.9.26补

Round 2 H

Solution 1:

考虑任意一个点u，已经计算了他所有子树v_i的答案，现在要计算v_i子树中强制经过u到v_j,j\neq i子树中点的答案以及以u为其中一个端点，子树中任意一个点作为另一个点的贡献。

对于点u，我们让他不在选定的集合T中：如果u在T中，那么当前经过u的所有答案贡献都会变为0；而对于位于两个不同子树中的点对(a,b)，路径上除了a,b以外的所有点都不能在T中；对于路径以外的点，不关心是否在T中。

1. 跨过u的不同子树中的贡献

   设链上的节点个数为\alpha =({\rm dep(x)}+{\rm dep(y)}-2{\rm dep(u)}+1)，路径长度为\alpha - 1，链以外点的个数为{\rm siz}(u)-\alpha，因此对于跨过u的贡献和就是

   \frac{1}{2}\sum_x\sum_{y,y不和x同一子树}\sum_{i\geq 0}^{{\rm siz}(u)-\alpha}\binom{{\rm siz(u)-\alpha}}{i}(i+2)(\alpha - 1)

   后面的和式化简一下，变成

   (\alpha - 1)(2^{{\rm siz(u)}-\alpha + 1}+k2^{{\rm siz(u)} - \alpha - 1})

2. 以u为端点的

   和刚才的方法一样，只不过现在只需要枚举子树中的点x，然后另一个端点设为u即可

   \sum_x(\alpha - 1)(2^{{\rm siz(u)}-\alpha + 1}+k2^{{\rm siz(u)} - \alpha - 1})

   发现处理了所有路径并且只跟路径长度有关，点分治即可，复杂度O(n \log n)

哦不对，要对x=1...n的每个长度统计路径个数，多了个ntt，复杂度O(n\log^2n)

Solution 2 :

我们发现对于距离为x的点对，会产生恒定的贡献。因为距离为x，所以链上点的个数为x+1，不在链上点的个数为n-x-1，这n-x-1个点可以随便选，然后乘上集合大小即可，跟 Solution 1 的处理相同，化为x2^{n-x}+x(n-x-1)2^{n-x-2}=x(n-x+3)2^{n-x-2}

对于根的移动，变成(x+\delta)(n-x+\delta + 3)2^{n-x+\delta-2}

然后换根 \rm dp维护\sum 2^{n-d-2}d(n-d+3),\sum d2^{n-d+3}, \sum 2^{n-d+3}, \sum 2^{n-d-2}(n-d+3)，注意g_{u,i},f_{u,i}的转移，处理的时候比较麻烦，要预处理出子树的答案

upd: 转移又臭又长，上面预处理子树答案是以子树为根的情况下，换根向子树内转移的时候，要先扣掉d(子树答案)，即距离+1的子树答案，然后把这部分对于子树来说是父向子树的答案距离再迭代+1，然后加上之前算出来的子树答案。