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
baobab: 2016-05-10 22:19:49

I'm getting NZEC Runtime Error, it looks like it's actually TLE but reported wrong. Has anyone managed to get a Java solution accepted?

Joe SeungHyun: 2015-01-06 23:43:31

I submitted my source written in C++ 4.3.2, but it made an error message : "Language available only on Cube Cluster". Why?

africamonkey: 2014-07-20 06:12:48

莫队好快。。RANK 4

hahaha: 2013-12-23 02:58:22

Orz 主席

ez_gx: 2013-04-26 13:20:50

为什么用莫队算法不能过

:D: 2012-05-18 06:22:48

COT3 doesn't exist. Just because there's COT2 and COT4 doesn't meant there has to be part 3.

亚夫结: 2012-05-18 03:26:54

Can you tell me how large the memory you give will be?

Last edit: 2012-05-18 03:28:39
亚夫结: 2012-05-18 02:27:41

Why can t we see COT3?

Last edit: 2012-05-18 03:27:39
Problem Solver: 2012-02-22 13:13:41

No doubt, cool problem !

@Problem Solver
Just enjoy it..

Last edit: 2012-03-04 05:16:06
Buda IM (retired): 2012-02-18 19:20:26

How large can weight of node be ?


@Buda IM
[0,2^31-1]

Last edit: 2012-02-20 10:10:39

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...