ADAFTBLL - Ada and Football
题意翻译
## 【题目大意】
你有一棵共 $n$ 个节点的树,一共有 $q$ 次操作,操作有两种分别为:
``1 x y`` :表示把第 $x$ 个节点的权值变成 $y$。
``2 u v`` :令 $s$ 表示每一种从 $u$ 号节点到 $v$ 号节点出现的权值的次数,输出 $\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``` 范围内
题目描述
Ada the Ladybug has many friends who live on a [tree](https://en.wikipedia.org/wiki/Tree_(data_structure)). Each of them is fan of a football team. Ada sometime go on a trip from one friend to another. If she meets a friend she tells him/her about all previously visited friends who are fans of the same team. The visited friend will gain **+1** happiness for each friend Ada told him/her about.
Ada is wondering (for each trip) what will be the total gaines happiness.
Also note that sometime a friend changes his/her mind and start to support different team.
输入输出格式
输入格式
The first line two integers **1 , the number of friends (**N**) and the number of queries.**
The next line will contain **N** integers **0, the team which **i $ ^{th} $** friend supports.**
The next **N-1** lines will contain two integers **0 , the friends which will be connected by a branch (edge).**
The next **Q** lines will be of two kinds:
**1 x y** (**0 , **0 ), meaning that **x $ ^{th} $** friend will start supporting team **y** (instead of the old one).****
**2 a b** (**0 ), meaning that Ada will travel from friend **a** to friend **b** and wants to know the happiness.**
输出格式
For each query of second kind, output the gained happiness.