最新要闻

广告

手机

顺络电子：董事长部分股权办理股票质押业务

顺络电子：董事长部分股权办理股票质押业务

 深圳7月二手住宅成交2259套，中介称近期咨询客户开始增加

深圳7月二手住宅成交2259套，中介称近期咨询客户开始增加

家电

  1. 首页
  2. 移动通信
  3. 内容

Crash 的文明世界 & JZPTREE & TREESUM 题解

来源：博客园

题意

给定一棵树，对于每个节点 \(u\)，求 \(\sum\limits_{v = 1}^{n} \operatorname{dist}(u, v) ^k\)，其中 \(\operatorname{dist(u, v)}\) 表示 \(u, v\) 两点间的距离。

题解

首先考虑化简算式中的 \(k\) 次幂，考虑使用斯特林数的性质：


(资料图片仅供参考)

\[n^k = \sum\limits_{i = 0}^{k} {n \choose i} \times i! \times {k \brace i}\]

所以可以化简原式

\[\begin{aligned}S(u) =& \sum\limits_{v = 1}^{n} \operatorname{dist}(u, v)^k \\=& \sum\limits_{v = 1}^{n} \sum\limits_{i = 0}^{k} {\operatorname{dist}(u, v) \choose i} \times i! \times {k \brace i} \\=& \sum\limits_{i = 0}^{k} i! \times {k \brace i} \sum\limits_{v = 1}^{n} {\operatorname{dist}(u, v) \choose i}\end{aligned}\]

设 \(\displaystyle f(u, i) = \sum\limits_{v = 1}^{n}{\operatorname{dist}(u, v) \choose i}\)，那么我们可以得到

\[S(u) = \sum\limits_{i = 0}^{k} i! \times {k \brace i} \times f(u, i)\]

下面考虑如何求出 \(\displaystyle f(u, i)\)，首先考虑子树的贡献，设 \(\displaystyle dp(u, i) = \sum\limits_{v \in \operatorname{subtree_u}}{\operatorname{dist}(u, v) \choose i}\)，发现对于 \(\displaystyle y \in \operatorname{\operatorname{son_u}}, v \in \operatorname{subtree_u}\)， 有 \(\operatorname{dist}(u, v) = \operatorname{dist}(y, v) + 1\)，考虑转移式

\[\begin{aligned}dp(u, i) =& \sum\limits_{v \in \operatorname{subtree_u}}{\operatorname{dist}(u, v) \choose i} \\=& \sum\limits_{y \in \operatorname{son_x}} \sum\limits_{v \in \operatorname{subtree_y}} {\operatorname{dist}(u, v) \choose i} \\=& \sum\limits_{y \in \operatorname{son_x}} \sum\limits_{v \in \operatorname{subtree_y}} {\operatorname{dist}(y, v) + 1 \choose i} \\=& \sum\limits_{y \in \operatorname{son_x}} \sum\limits_{v \in \operatorname{subtree_y}} {\operatorname{dist}(y, v) \choose i} + {\operatorname{dist}(y, v) \choose i - 1} \\=& \sum\limits_{y \in \operatorname{son_x}} dp(y, i) + dp(y, i - 1)\end{aligned}\]

上述的推导使用了杨辉三角的递推式：

\[{n \choose m} = {n - 1 \choose m} + {n - 1 \choose m - 1}\]

这样我们就可以从叶子节点向上更新出每个节点的 \(dp(u, i)\) 值了。接下来考虑求出 \(f(u, i)\) 的值，记 \(fa\) 为 \(u\) 的父亲节点，发现对于 \(\displaystyle v \in \operatorname{subtree_u}\)，有 \(\operatorname{dist}(u, v) = \operatorname{dist}(fa, v) - 1\)；对于 \(v \notin \operatorname{subtree_u}\)，有 \(\operatorname{dist}(u, v) = \operatorname{dist}(fa, v) + 1\)，考虑转移式

\[\begin{aligned}f(u, i) =& \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(u, v) \choose i} + \sum\limits_{v \notin \operatorname{subtree_u}} {\operatorname{dist}(u, v) \choose i} \\ =& \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) - 1 \choose i} + \sum\limits_{v \notin \operatorname{subtree_u}} {\operatorname{dist}(fa, v) + 1 \choose i} \\ =& \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i} - \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) - 1 \choose i - 1} + \\&\sum\limits_{v \notin \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i} + \sum\limits_{v \notin \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i - 1} \\ =& \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i} + \sum\limits_{v \notin \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i} - \\&\sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) - 1 \choose i - 1} + \sum\limits_{v \notin \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i - 1} \\ =& \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i} + \sum\limits_{v \notin \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i} + \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i - 1} + \\&\sum\limits_{v \notin \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i - 1} - \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i - 1} - \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) - 1 \choose i - 1} \\ =& f(fa, i) + f(fa, i - 1) - \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) \choose i - 1} - \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) - 1 \choose i - 1} \\ =& f(fa, i) + f(fa, i - 1) - \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) - 1 \choose i - 1} - \\&\sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) - 1 \choose i - 2} - \sum\limits_{v \in \operatorname{subtree_u}} {\operatorname{dist}(fa, v) - 1 \choose i - 1} \\ =& f(fa, i) + f(fa, i - 1) - 2dp(u, i - 1) - dp(u, i - 2)\end{aligned}\]

上述推导中均运用了杨辉三角递推式。利用推导出的转移式我们可以以 \(\mathcal{O}(nk)\) 的复杂度处理出 \(f(u, i)\) 的值，同时我们可以以 \(\mathcal{O}(k^2)\) 的复杂度预处理出需要的斯特林数，再代入 \(S(u)\) 的表达式即可求出答案，总复杂度为 \(\mathcal{O}(nk + k^2)\)。

Code

出于篇幅考虑，代码放在云剪切板中。

  • SP7363 TREESUM - Tree Sum

  • P4827 [国家集训队] Crash 的文明世界

关键词：