算是个简单题吧。
首先列个暴力式子：
\[ \sum_G \sum_{i = 1}^n d_i^k \]
发现很不现实。我们考虑把点拆开来考虑，因为全集里面可以直接独立的来算。考虑某个点度数为 \(x\) 的方案数，就变成了：
\[ n \sum_{x = 0}^{n – 1} x^k f(x) \]
其中 \(f(x)\) 代表的是一个图某个点的度数为 \(x\) 的方案数。其实稍微思考下就知道，我们可以把这个点剥离出来，强制连边之后再生成一个图即可：
\[ \begin{aligned} f(x) &= {n – 1 \choose x} 2^{n – 1 \choose 2} \\ ans &= n \sum_{x = 0}^{n – 1} x^k {n – 1 \choose x} 2^{n – 1 \choose 2} \\ &= n2^{n – 1 \choose 2} \sum_{x = 0}^{n – 1} x^k {n – 1 \choose x} \end{aligned} \]
一眼可以了解到是一道割点题。对于不是割点的情况，那么被计算的点对一定包含此点本身，又因为有序，所以贡献就是\(2(n – 1)\)。如果是割点的话，就比较麻烦，分下面几个来算：
第一个很好算，是\(2(n – 1)\)。第二个，在 Tarjan 枚举搜索子树的时候计算子树大小和全图补集的乘积（注意，这里会多计算一遍与点\(u\)的点对，所以我们第一个改成算\(n – 1\)）；第三个，算「当前整颗搜索树与图的补集大小」与「搜索树的大小」的乘积。
综合起来就是，对于点\(u\)：
\[ ans_u = \sum_{k \in son(u)} (n – size(k)) \times size(k) + (n – 1) + (n – 1 – \sum_{k \in son(u)} size(k)) \times (1 + \sum_{k \in son(u)} size(k)) \]
kal0rona 越来越 sb了。
可以把整个思路转换为 CDQ 分治下的二位数点。\(x\)轴就代表正常的物理距离的轴，然后\(y\)轴就代表信号接收的轴，把一个询问拆掉成为容斥的形式即可。
由于本人分治很菜，所以就来刷分治题了。
先思考 50 分\(O(n^2)\)的做法。记录每一个位置的原始值、变化后的最大值、变化后的最小值，然后发现如果一个位置\(i\)对后面的位置\(j\)有贡献当且仅当：
\[a_i < minVal_j \ (1) \\ maxVal_i < a_j \ (2) \]
所以这就相当于一个二位偏序的题目，有两个限制。我们可以用整体二分，在做完左区间之后，左区间按原来的值进行排序，而右区间按最小值进行排序，即可满足第一个条件；第二个条件可以用线段树来搞，搞两个指针来比较大小，然后用线段树来统计答案即可。非常好写。