CF274B Zero Tree

一棵树是一个包含 $n$ 个顶点和恰好 $n-1$ 条边的图，并且该图需满足下述条件：对任意一对顶点，存在唯一一条按照边的数量计算长度的最短路径。 树 $T$ 的子树是指顶点集合和边集合均为 $T$ 的子集的树。 现在给定一棵有 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。此外，每个顶点上都写有一个整数。最开始，第 $i$ 个顶点上写的整数为 $v_{i}$。每次操作，你可以进行以下操作之一： 1. 选择包含编号为 $1$ 的顶点的一个子树。 2. 将该子树上所有顶点的整数都加一或者减一。 请你计算，使得所有顶点上书写的整数均变为零，所需的最少操作次数。

输入的第一行包含一个正整数 $n$（$1 \leq n \leq 10^5$）。 接下来 $n-1$ 行，每行包含两个整数 $a_{i},\ b_{i}$（$1 \leq a_{i}, b_{i} \leq n,\ a_{i} \ne b_{i}$），表示在顶点 $a_{i}$ 和顶点 $b_{i}$ 之间有一条边。保证输入的图是一棵树。 最后一行包含 $n$ 个用空格分隔的整数 $v_1, v_2, \ldots, v_n$（$|v_i| \leq 10^9$）。

输出一个整数，表示使所有顶点上的整数均变为零所需的最小操作次数。 请不要在 C++ 代码中使用 %lld 读写 64 位整数。推荐使用 cin、cout 流或 %I64d 格式符。

由 ChatGPT 5 翻译