题目描述

在操作系统的文件资源管理器中，我们经常需要查看某个文件夹占用了多少磁盘空间。为了简化模型，我们将文件系统抽象为一棵有根树，每个节点都有一个大小 $s_i$：目录节点大小为 $0$，文件节点大小为正整数。

现在给定这棵树的结构，请你计算并输出每个节点所占用的磁盘空间：

• 如果节点是目录节点，则输出该目录下所有文件（即其子树中所有叶子节点）的大小之和。
• 如果节点是文件节点，则输出其本身的大小。

输入格式

第一行一个整数 $n$，表示节点数量。
接下来 $n - 1$ 行，每行包含三个整数 $u, v, s_v$，表示节点 $u$ 是节点 $v$ 的父节点，且节点 $v$ 的大小为 $s_v$。

• 若 $v$ 是目录节点，则 $s_v = 0$。
• 若 $v$ 是文件节点，则 $s_v$ 为其文件大小（正整数）。

保证所有边构成以节点 $1$ 为根的有向树。

输出格式

输出一行 $n$ 个整数，用空格分隔，第 $i$ 个数表示节点 $i$ 的实际占用大小。

5
1 2 0
1 3 0
2 4 100
2 5 200

300 300 0 100 200

数据规模与约定

样例说明

• 节点 4、5 为文件节点，大小分别为 100、200。
• 节点 2 为目录节点，其子树中文件总大小为 100 + 200 = 300。
• 节点 3 为空目录，因此占用大小为 0。
• 节点 1 为根目录，其子树中文件总大小为 100 + 200 = 300。

数据范围

• $1 \le n \le 10^5$

• 对于所有文件节点，$1 \le s_v \le 10^9$

• 对于所有目录节点，$s_v = 0$