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
bekh: 2019-07-06 18:34:06

Range of the weight is big and using map will get timelimit. Use compression.

pan1640616850: 2019-07-04 16:47:21

10 1
1 2 3 4 5 6 7 8 9 10
2 1
3 2
4 2
5 4
6 2
7 6
8 3
9 1
10 2
1 3

ans:3

10 1
1 2 3 4 5 6 7 8 9 10
2 1
3 1
4 2
5 4
6 3
7 5
8 2
9 4
10 7
5 9

ans:3

sagarthecoder: 2018-11-28 21:04:37

What is the Limit of Weight???????????

Luis Manuel Díaz Barón: 2017-12-23 06:34:45

What is the limit for the weight of each node?

dazzler__: 2017-09-01 17:20:06


what will be the answer of this testcase:
10 1
9 4 10 7 3 6 1 8 2 5
3 1
7 2
3 4
3 5
2 6
3 7
2 8
7 9
9 10
8 1

fly_sky12: 2017-05-15 16:22:45

I think it has strict time limit.
@gustavonunes each input has only one test case.

Last edit: 2017-05-15 16:24:13
gustavonunes: 2017-02-14 01:25:28

Input has several test cases... Gave me a lot of WA

virus_1010: 2017-02-10 20:02:04

Can it be done in less than O(n*sqrt(n)) ?

laofu: 2017-01-30 15:33:34

what is the range of weight?

AASHISH KUMAR: 2016-05-21 11:26:50

nice problem

Last edit: 2016-12-25 06:23:17

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