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

AASHISH KUMAR:
20160521 11:26:50
nice problem Last edit: 20161225 06:23:17 

baobab:
20160510 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:
20150106 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:
20140720 06:12:48
莫队好快。。RANK 4 
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... 