给定一个 $n$ 个节点的有根树，开始时每个节点的权值都为 $0$ 。一共有 $q$ 个时刻，每个时刻可能有如下两个操作之一：

1. 给定一个节点 $x$ ，从下一个时刻起每个时刻都给该节点的权值 $+1$（每个节点只会有一次该操作）；

2. 给定两个节点 $x,y$ 以及一个数 $C$ ，求这两个节点的简单路径上权值大于 $C$ 的节点个数，以及简单路径上的所有节点个数。

给出一个 $n$ 个节点的有根树。有 $q$ 次询问，每次询问给出 $l,r,z$ ，求 $\sum _ {l \leq i \leq r}dep[LCA(i,z)]$ 。

给定一棵 $n$ 个节点的树，对于每个点都有两个权值 $w_i,c_i$ 。

存在 $m$ 个操作，分为4类。

• “CC x c”：将 $c_x$ 更改为 $c$ ；

• “CW x w”：将 $w_x$ 更改为 $w$ ；

• “QS x y”：对所有满足在 $x$ 到 $y$ 路径上且 $c_i = c_x = c_y$ 的节点 $i$，求 $\sum w_i$ ；

• “QM x y”：对所有满足在 $x$ 到 $y$ 路径上且 $c_i = c_x = c_y$ 的节点 $i$ ，求 $\max(w_i)$ ；

对于后两个操作，保证 $c_x = c_y$ 。

你决定设计你自己的软件包管理器。如果软件包 A 依赖软件包 B ，那么安装软件包 A 以前，必须先安装软件包 B 。同时，如果想要卸载软件包 B ，则必须卸载软件包 A 。现在你已经获得了所有的软件包之间的依赖关系。除 $0$ 号软件包以外，所有软件包都会依赖一个且仅一个软件包，而 $0$ 号软件包不依赖任何一个软件包。依赖关系不存在环。

现在有一些安装或卸载软件包的操作，需要求出这个操作实际上会改变多少个软件包的安装状态（即安装操作会安装多少个未安装的软件包，或卸载操作会卸载多少个已安装的软件包）。

给定一棵有 $n$ 个节点的无根树和 $m$ 个操作，操作有两类：

• 将节点 $a$ 到节点 $b$ 路径上所有点都染成颜色 $c$ ；
• 询问节点 $a$ 到节点 $b$ 路径上的颜色段数量（连续相同颜色被认为是同一段），

如“112221”由3段组成：“11”、“222”和“1”。

请你写一个程序依次完成这 $m$ 个操作。

给定一颗 $n$ 个节点的树，节点编号为 $1$ 到 $n$ ，每个节点都有一个权值 $w_i$ 。

有以下三种操作或询问：

I. CHANGE u t : 把结点 $u$ 的权值改为 $t$

II. QMAX u v: 询问从点 $u$ 到点 $v$ 的路径上的节点的最大权值

III. QSUM u v: 询问从点 $u$ 到点 $v$ 的路径上的节点的权值和