[HDU5709]Claris Loves Painting(线段树合并,主席树)

发布于 2018-02-18  332 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[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}.

Http

HDU

Tag

线段树合并,主席树

题目大意

一棵有根树,树上每一个点有可能相同的颜色,现在要求回答若干个询问,求在\(u\)的子树内与\(u\)相距不超过\(d\)的点有多少种颜色。强制在线。

解决思路

先不考虑颜色的限制,假设问题是询问在一个点的子树中与\(u\)相距不超过\(d\)的节点个数,那么这个可以用线段树来维护。具体来说,对于每一个点维护一棵线段树,线段树维护的区间\([l,r]\)表示深度在\([l,r]\)内的节点个数。这个可以直接从儿子线段树合并转移过来。
再考虑加上颜色的限制。由于一种颜色只算一次,不妨我们对于每一种颜色就只算深度最浅的那个,那么我们对于每一个点再维护一棵线段树,这个树中的第\(i\)号位置维护在这棵子树内颜色为\(i\)的最浅的点的深度,那么,合并的时候就取两者中更浅的那个点作为当前的值,然后由于这时颜色有了冲突,于是再修改第一棵线段树中的值,具体来说就是在第一棵线段树中把更深的那个减掉,因为如果我们依次合并的话一次只会有一个冲突。
直接这么做是会爆空间的,考虑到实际从下往上合并的时候,实际用到的空间并不多,并且还有很多重复,所以可以借助主席树的思想,动态开点并重复利用已知信息。
另外,由于题目中给出了一个点的父亲编号小于自己的编号,所以树\(dfs\)可以直接用\(for\)代替。
少用\(memset\)。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU5709]Claris Loves Painting(线段树合并,主席树)


HNCJ OIer