Tree
题号:NC213223
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

给定一个具有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的最近公共祖先。我们认为俩个点对是不同的,只要满足xy至少一个不同。

输入描述:

输出描述:

共一行,一个整数表示满足的点数对。
示例1

输入

复制
3
1 1 1
1 2
1 3

输出

复制
2

说明

只有点数对(2,3)和(3,2)满足要求