题目描述

给定一棵以 $1$ 为根，包含 $N$ 个节点的有根树，每个节点有一个初始权值。需要处理 $M$ 次操作，操作分为三种类型：

1. 类型 1：将节点 $x$ 的点权增加 $a$
2. 类型 2：将以节点 $x$ 为根的子树中所有节点的点权都增加 $a$
3. 类型 3：查询从节点 $x$ 到根节点 $1$ 的路径上所有节点的点权之和

输入格式

• 第一行：两个整数 $N, M$，表示节点数和操作数
• 第二行：$N$ 个整数，表示各节点的初始权值
• 接下来 $N-1$ 行：每行两个整数 $fr, to$，表示树中的一条边
• 接下来 $M$ 行：每行表示一个操作
  • 操作 1：1 x a
  • 操作 2：2 x a
  • 操作 3：3 x

输出格式

对于每个类型 3 的操作，输出一行答案。

数据范围

• $1 \leq N, M \leq 10^5$
• 所有输入数据的绝对值不超过 $10^6$

算法分析

问题难点

1. 子树操作：需要高效处理以任意节点为根的子树修改
2. 路径查询：需要快速计算从任意节点到根的路径和
3. 大规模数据：$N, M \leq 10^5$，需要 $O(n \log n)$ 或 $O(n \log^2 n)$ 的算法

核心思路：树链剖分

树链剖分可以将树结构转化为线性序列，从而利用线段树等数据结构高效处理。

基本概念

1. 重儿子：节点 $x$ 的所有儿子中子树大小最大的儿子
2. 重链：由重儿子连接形成的链
3. 轻边：非重边
4. DFS 序：通过特定的 DFS 遍历顺序为节点编号

剖分过程

1. 第一次 DFS：

   • 计算子树大小 $size[x]$
   • 确定重儿子 $son[x]$
   • 计算节点深度 $dep[x]$ 和父节点 $fa[x]$

2. 第二次 DFS：

   • 优先遍历重儿子，保证重链在 DFS 序中连续
   • 记录每个节点的 DFS 序 $dfn[x]$
   • 记录每个节点所在重链的顶端 $top[x]$

数据结构设计

线段树维护

建立线段树维护 DFS 序列，支持：

• 区间加：用于子树修改
• 区间求和：用于路径查询

操作处理

1. 单点修改（类型 1）：

   • 直接在线段树的 $dfn[x]$ 位置加上 $a$

2. 子树修改（类型 2）：

   • 子树在 DFS 序中对应区间 $[dfn[x], dfn[x] + size[x] - 1]$
   • 对该区间执行区间加操作

3. 路径查询（类型 3）：

   • 从节点 $x$ 开始，不断向上跳转到链顶
   • 对于每条链 $[top[x], x]$，查询对应区间和并累加
   • 直到到达根节点

算法流程

1. 预处理阶段：

   进行两次 DFS，完成树链剖分
   根据 DFS 序建立线段树
   

2. 操作处理阶段：

   for 每个操作：
       if 类型1: 线段树单点加(dfn[x], a)
       if 类型2: 线段树区间加(dfn[x], dfn[x]+size[x]-1, a)  
       if 类型3: 
           res = 0
           while x != 0:
               res += 线段树区间和(dfn[top[x]], dfn[x])
               x = fa[top[x]]
           输出 res
   

复杂度分析

• 预处理：两次 DFS，$O(N)$
• 单点/子树操作：线段树操作，$O(\log N)$
• 路径查询：$O(\log N)$ 次链跳转，每次 $O(\log N)$，总共 $O(\log^2 N)$
• 总复杂度：$O(N + M \log^2 N)$，可以满足题目要求

实现细节

1. DFS 序性质：

   • 重链在 DFS 序中连续
   • 子树在 DFS 序中连续

2. 线段树实现：

   • 需要支持懒标记的区间加和区间求和
   • 注意数据范围，使用 long long 存储结果

3. 边界处理：

   • 根节点的处理
   • 空子树的处理

总结

本题是树链剖分的经典应用，通过将树结构线性化，可以高效处理子树修改和路径查询。关键在于理解树链剖分的原理和 DFS 序的性质，以及如何利用线段树维护序列信息。