COT2 - Count on a tree II

题意翻译

## 题目描述 给定一个n个节点的树，每个节点表示一个整数，问u到v的路径上有多少个不同的整数。 ## 输入格式 第一行有两个整数n和m（n＝40000，m＝100000）。 第二行有n个整数。第i个整数表示第i个节点表示的整数。 在接下来的n-1行中，每行包含两个整数u v，描述一条边（u，v）。 在接下来的m行中，每一行包含两个整数u v，询问u到v的路径上有多少个不同的整数。 ## 输出格式 对于每个询问，输出结果。 贡献者：つるまる

题目描述

You are given a tree with **N** nodes. The tree nodes are numbered from **1** to **N**. Each node has an integer weight. We will ask you to perform the following operation: - **u v** : ask for how many different integers that represent the weight of nodes there are on the path from **u** to **v**.

输入输出格式

输入格式

In the first line there are two integers **N** and **M**. (**N** <= 40000, **M** <= 100000) In the second line there are **N** integers. The i-th integer denotes the weight of the i-th node. In the next **N-1** lines, each line contains two integers **u** **v**, which describes an edge (**u**, **v**). In the next **M** lines, each line contains two integers **u** **v**, which means an operation asking for how many different integers that represent the weight of nodes there are on the path from **u** to **v**.

输出格式

For each operation, print its result.

输入输出样例

输入样例 #1

``````8 2
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5
7 8``````

输出样例 #1

``````4
4``````