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 ith integer denotes the weight of the ith node.
In the next N1 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
zhangzhongyu:
20190926 05:02:40
Last edit: 20190926 05:44:22 

bekh:
20190706 18:34:06
Range of the weight is big and using map will get timelimit. Use compression. 

pan1640616850:
20190704 16:47:21
10 1


sagarthecoder:
20181128 21:04:37
What is the Limit of Weight??????????? 

Luis Manuel Díaz Barón:
20171223 06:34:45
What is the limit for the weight of each node? 

dazzler__:
20170901 17:20:06


fly_sky12:
20170515 16:22:45
I think it has strict time limit.


gustavonunes:
20170214 01:25:28
Input has several test cases... Gave me a lot of WA


virus_1010:
20170210 20:02:04
Can it be done in less than O(n*sqrt(n)) ? 

laofu:
20170130 15:33:34
what is the range of weight? 
Added by:  Fotile 
Date:  20120217 
Time limit:  1.207s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Just for fun... 