COT2 - Count on a tree II


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.

Input

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.

Output

For each operation, print its result.

Example

Input:
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

Output:
4
4

hide comments
cyb1010: 2023-10-13 03:21:17

Can anybody hack my submission? Got WA many times.

dan_4_life: 2023-04-08 15:59:12

Solvable with small to large merging too.

mahabub618: 2023-01-26 17:34:04

Nice problem. AC in one go using Mo's with tree.

lzwhindsers: 2022-11-15 05:52:17

who can hack my solution,I have got WA many times.

lzwhindsers: 2022-11-15 05:35:27

Hello,friends from Poland,I'm from China.

Last edit: 2022-11-15 05:36:58
implicit__: 2021-09-07 11:02:55

Can it be solved using hld ?

z_s_meem: 2021-08-24 18:36:33

@hacker_sk, no.. N<=40000 is fine... but you need data compression for weights

irrr: 2021-07-29 06:00:48

NGUYEN XUAN HIEU HAI PHONG VO DOI
KING HIEU IS BACK
EZ GAME EZ LIFE

Last edit: 2021-08-03 09:44:01
princemishra: 2021-02-11 18:01:31

things to use
1. path queries using mo's algorithm
2. co-ordinate compression
3. n <= 100000
4. there is more than one test case.

sarkybastard: 2020-09-24 23:40:21

Nope. youre gettign WA on any test case


Added by:Fotile
Date:2012-02-17
Time limit:1.207s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Just for fun...