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.
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.
For each operation, print its result.
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
Last edit: 2019-09-26 05:44:22
Range of the weight is big and using map will get timelimit. Use compression.
What is the Limit of Weight???????????
Luis Manuel Díaz Barón:
What is the limit for the weight of each node?
I think it has strict time limit.
Input has several test cases... Gave me a lot of WA
Can it be done in less than O(n*sqrt(n)) ?
what is the range of weight?