HBC213223数据结构Tree题解（满足x不是y的祖先）

柳絮泡泡算法基础篇 2023-11-08 20:59:03 38 0

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

给定一个具有n个顶点，n- 1条边的以1为根的树，每个点都有权值val[i]，求有多少不同点对(x,y)，满足x不是y的祖先，y不是x的祖先，并且val[x]+val[y] == 2*val[lca(x,y)]，其中lca(x,y)代表x和y的最近公共祖先，我们认为俩个点对是不同的，只要满足x和y至少一个不同。

给定一个具有n个顶点，n - 1条边的以1为根的树，每个点都有权值val[i]。求有多少不同点对(x,y)。满足x不是y的祖先，y不是x的祖先，并且val[x]+val[y] == 2*val[lca(x,y)]。其中lca(x,y)代表x和y的最近公共祖先。我们认为俩个点对是不同的，只要满足x和y至少一个不同。