# [HDU5709]Claris Loves Painting（线段树合并，主席树）

### Description

Claris loves painting very much, so he painted a tree with beautiful colors.
The tree is a rooted tree with n nodes which are conveniently labeled by 1,2,...,n. Its root is the 1-st node, and the i-th node is painted with color ci. If ci=cj, then we think these two nodes have the same color.
We define depthi as the distance between the i-th node and the root, and simply, the distance between two adjacent nodes is always 1.
Standing in front of this beautiful tree, Claris comes up with m questions.
In each question, there are two integers x and d, which means that Claris wants to know the number of different kinds of colors occur in S, where S={v|v in x′s subtree and depthv≤depthx+d}.

HDU

HNCJ OIer