Explanation Of A CPP Problem

Prompt

**题目：** # 圣诞树（tree） ## 【题目描述】 小 P 有一棵 n 个节点的树（显然有 \(n-1\) 条边），现在他想把该棵树当作一棵圣诞树，于是给每个节点挂上了一个彩灯，每个节点 u 上彩灯都有一个美丽值 \(w_u\)。为了使得圣诞树不那么单调所以所有节点的美丽值均互不相同。 除了彩灯以外，小 P 还要给这棵圣诞树上一条彩带，彩带位于树上的一条路径，而对于彩带路径上的每个点 u，假设路径上有 \(s_u\) 个点的彩灯美丽值不大于 \(w_u\)（包括 u 自己），那么它对彩带的美丽贡献就是 \(s_u \cdot w_u\)。于是彩带的美丽值就是其路径上所有点对其美丽值的贡献的和。 小 P 想请你求出当选择任意一点对 \(x, y (x < y)\) 作为彩带路径的两端点时，彩带的美丽值的和是多少。由于答案很大所以你只需要求出答案对 \(10^9 + 7\) 取模的结果即可。 --- ## 【输入格式】 从文件 tree.in 中读入数据。 第一行输入一个整数 \(n\)。 第二行输入 n 个整数表示每个节点彩灯的美丽值 \(w_1, w_2, \ldots, w_n\)。 接下来 \(n-1\) 行每行两个整数 \(u, v\) 表示树上一条边。 --- ## 【输出格式】 输出到文件 tree.out 中。 输出一行一个整数表示答案。 --- ## 【样例 1 输入】 3 4 9 25 2 1 3 1 --- ## 【样例 1 输出】 211 --- 第 7 页 共 8 页 --- 模拟赛 4 圣诞树（tree） --- ## 【样例 2】 见下发文件中的 `tree/ex_tree2.in` 与 `tree/ex_tree2.ans`。 ## 【样例 3】 见下发文件中的 `tree/ex_tree3.in` 与 `tree/ex_tree3.ans`。 ## 【样例 4】 见下发文件中的 `tree/ex_tree4.in` 与 `tree/ex_tree4.ans`。 --- ## 【测试点约束】 对于 25% 的数据，满足 \(n, q \leq 2000\)。 对于 40% 的数据，满足 \(n, q \leq 10^4\)。 对于另外 15% 的数据，满足对于第 i 条边，\(u = i, v = i+1\)。 对于另外 15% 的数据，满足对于第 i 条边，\(v = i+1, u \in [1, i]\) 中的所有整数中等概率选择。 对于全部数据，满足 \(1 \leq n \leq 5 \times 10^5, 1 \leq w_i \leq 10^9 + 6\)，保证给出的 \(n-1\) 条边构成一棵树。保证所有 \(w_i\) 互不相同。 --- **题解：** # 圣诞树 仍然考虑贡献，一对点 \((x, y)(w_y \leq w_x)\) 的贡献就是 \(w_x \times\) 包含 \(x, y\) 的路径数量，而后者就是两点两侧点数的积。 考虑分类讨论，假如 \(x\) 是 \(y\) 的祖先，那么相当于子树查询，用 DFS 序可以转化为二维数组。 如果 \(y\) 是 \(x\) 的祖先，那么相当于路径查询，可以 DFS 的时候用数据结构直接维护。否则就是 \(x, y\) 不互为祖孙关系，可以用全部的减去前两种情况。 数据结构直接维护即可，时间复杂度 \(O(n \log n)\)。给我讲解一下这道题，从思路开始，分段写出C++代码，最后给出带有详细注释的完整代码