题目内容

小美有一棵 $n$ 个结点的树，树上第 $i$ 个结点的权值为 $a_i$ 。

现在她定义树上任意两点 $u,v$ 的距离为 $dist(u,v)$ ，即树上两点间简单路径的边数。

现在她提出 $9$ 次操作，每次操作给定三个整数 $u,v,x$ ，她准备从 $u$ 出发，把 $u→v$ 简单路径上的结点权值，按节点在路径上出现的先后顺序，依次加上 $x,x+1,x+2,...,x+ dist(u,v)$ 。请你输出操作后所有结点的权值。

题目理解

给定一个树，树的节点上有权值。对于每次操作，指定两节点 $u$ 和 $v$，我们需要从节点 $u$ 到节点 $v$ 的路径上，按路径的顺序给节点增加一定的权值。增加的权值是从 $x$ 开始，依次递增。

思路与方法

1. 路径计算

在树上，任意两点之间有且仅有一条简单路径。因此，我们首先需要能够高效地计算出两点之间的路径。这个问题的关键是如何快速找到路径，并在路径上更新权值。