塔子哥学算法

未归档 LCA，数学 - 牛客练习赛55 E.树

未归档

题解(1)

/ 注册

LCA，数学 - 牛客练习赛55 E.树

815 浏览 0 回复 2019-12-14

塔子哥学算法

+关注

题意:

首先n为1e6,优先找规律。我们可以发现，边长都为1，最后的答案只跟树的结构有关。所以从数学的角度出发找公式。

设 $dis(x,y)$ 为x,y两点的距离, $f(x)$ 为x点的深度, $ff为\sum_{x = 1}^nf^2(x)$

$size(i)为以i为根节点的子树的大小$ , $sum(i)为以i为根节点的子树f(x)的和$ .

由LCA的知识我们知道:

$\text{[math]}$

那么 $\text{[math]}$

上面右式总共分为五个部分:我们一个一个来分析.

对于 $\text{[math]}$

$\sum_{x=1}^n \sum_{y=1}^nf^2(x) = \sum_{x=1}^nf^2(x) \sum_{y=1}^n 1=ff*size(1) （以1号点为整棵树的根节点）$

对于 $\text{[math]}$

$\sum_{x=1}^n\sum_{y=1}^n2f(x)f(y) = 2\sum_{x=1}^nf(x)\sum_{y=1}^nf(y) =2sum^2(1)$

显然,前三项可以最后再算。

对于 $\text{[math]}$ ,不好直接处理，那么我们枚举 $\text{[math]}$

$原 =4\sum_{lca(x,y) = i}f^2(i) = 4f^2(i)\sum_{lca(x,y) = i}1$

对于上面式子, 显然我们只需要找到树中 $\text{[math]}$ 的所有点对数.

根据容斥定理我们可以发现一棵树中以某一点 $i$ 为 $lca$ 的x,y的点对数为 $size^2(i) - \sum_{j∈son(i)}size^2(j)$ .

关于式子的理解:首先,如果(x,y)两个点在i的不同子树中或其中一点为i点,那么就会有贡献。

$\text{[math]}$ ,需要减去处在同一颗子树里的点对 $\sum_{j∈son(i)}size^2(j)$ .

对于 $\text{[math]}$ 有:

$\sum_{lca(x,y) = i}4f(i) * ( f(x) + f(y)) =4f(i) \sum_{lca(x,y) = i} ( f(x) + f(y))$

根据上式我们还需要知道 $\sum_{lca(x,y) = i}(f(x) + f(y))$ .

$其=2\sum_{j∈son(i)}sum(j)*(size(i) - size(j)) + 2f(i)*size(i)$

关于式子的理解:点对(x,y),我们按子树来考虑每个点对答案的贡献.

心得：

①数据量大，又发现边长为1，优先从数学(找规律)的角度出发优化时间复杂度.

②在边长固定为1的情况下求一棵树的所有路径和dis(x,y)，将其转化为lca去思考.

③记得取模问题，开long long ,该取模的都要取模!!

AC代码:

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42517431

举报

收藏

赞

评论加载中...