SP32952 ADAFTBLL - Ada and Football
题目描述
你有一棵共 $n$ 个节点的树，节点编号从 $0$ 开始。一共有 $q$ 次操作，操作有两种，分别为：
``1 x y`` ：表示把第 $x$ 个节点的权值变成 $y$。
``2 u v`` ：对于每一种出现在 $u$ 号节点到 $v$ 号节点最短路径上的权值，令 $s$ 表示这种权值在路径上出现的次数，输出 $\sum\dfrac{s \times (s - 1)}{2}$ 。
输入格式
第一行两个整数 $n,q$。
第二行 $n$ 个整数 $a_0,a_1,\dots a_{n-1}$，表示该树上每一个节点的权值。
第三到第 $1+n$ 行，每行两个整数 $u$ 和 $v$，表示节点 $u$ 和节点 $v$ 之间有边连接。
接下来 $q$ 行，表示题目所述操作。
输出格式
输出每一次询问的答案。
## 【样例】
``in``
```
7 8
0 0 1 2 1 1 2
0 1
1 5
1 2
2 4
2 3
3 6
2 4 5
2 0 6
2 1 3
1 1 2
1 2 2
2 4 5
2 0 6
2 1 3
```
``out``
```
3
2
0
2
6
3
```
说明/提示
$1 \le n\ ,\ q,\ \forall a_i \le 10^5$，$0\le y \le 10^5$，$0\le x,u,v< n$。
保证输入的所有数字在 ```int``` 范围内