练习 12：树上差分

题目描述：

给定一棵以 1 为根的有根树，有 n 个结点。现在要进行 m 次操作，每次操作选择一条从 u 到 v 的路径，将路径上所有结点的权值都加上 k。

所有操作完成后，输出每个结点的最终权值。

输入格式：

• 第一行：两个正整数 n, m（2 ≤ n ≤ 10000，1 ≤ m ≤ 10000）
• 第二行：n-1 个正整数 f_2, f_3, ..., f_n，其中 f_i 表示结点 i 的父结点编号
• 接下来 m 行：每行三个整数 u, v, k，表示将路径 u → v 上所有结点的权值加上 k（1 ≤ k ≤ 1000）

输出格式：

• 一行，n 个整数，表示每个结点的最终权值

样例输入：

5 3
1 1 2 2
1 4 2
2 5 3
1 3 1

样例输出：

3 3 1 2 3

样例解释：

初始所有结点权值为 0。

操作1：路径 1 → 4，结点 1, 2, 4 各加 2 → [2, 2, 0, 2, 0]
操作2：路径 2 → 5，结点 2, 5 各加 3 → [2, 5, 0, 2, 3]
操作3：路径 1 → 3，结点 1, 3 各加 1 → [3, 5, 1, 2, 3]

但样例输出是 [3, 3, 1, 2, 3]，可能路径计算方式不同。

提示：

• 树上差分的核心思想：

  • 对于路径 u → v 的修改，可以拆成：
    • u 到根的路径 +k
    • v 到根的路径 +k
    • lca(u,v) 到根的路径 -k（减一次，因为被加了两次）
    • lca(u,v) 的父结点到根的路径 -k（如果存在）

• 实现步骤：

  1. 预处理 LCA（最近公共祖先）
  2. 对每次操作 (u, v, k)：
     • diff[u] += k
     • diff[v] += k
     • diff[lca(u,v)] -= k
     • diff[fa[lca(u,v)]] -= k（如果父结点存在）
  3. DFS 后序遍历，从叶子向上累加差分数组

• 简化版（如果不需要 LCA）：

  • 对于路径 u → v，可以暴力遍历路径上的所有结点
  • 但时间复杂度 O(m * n)，可能超时