主题

主题

 
   

3307: 雨天的尾巴

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=3307

Description

N个点,形成一个树状结构。有M次发放,每次选择两个点x,y,对于x到y的路径上(含x,y)每个点发一袋Z类型的物品。完成所有发放后,每个点存放最多的是哪种物品。

Input

第一行数字N,M

接下来N-1行,每行两个数字a,b,表示a与b间有一条边

再接下来M行,每行三个数字x,y,z.如题

Output

输出有N行

每i行的数字表示第i个点存放最多的物品是哪一种,如果有

多种物品的数量一样,输出编号最小的。如果某个点没有物品

则输出0

Sample Input

(样例过长不适合搬上来)

Sample Output

(样例过长不适合搬上来)

1<=N,M<=100000

1<=a,b,x,y<=N

1<=z<=10^9


个人解法:

(有没有过样例不知道)


一个很简单的想法就是,每个节点维护一个集合,然后从叶子合并上来,维护集合的最大值以及最大值的编号即可。

可以用Splay的启发式合并。也可以用权值线段树合并。

这个故事告诉我们,权值线段树是替代Splay的有效容器。线段树合并更是代替启发式合并的优秀合并方式。

代码如下:

https://code.csdn.net/snippets/2289869


一个更加高明的算法:

我们做出树链剖分的序。现在把问题变为了区间问题。

对这个序列做差分,变为单点修改前缀查询。

用一个以zi为下标的线段树,维护zi这个物品出现的次数,并维护出现次数的最大值以及节点。从左往右扫过去即可。

我却更喜欢这个方法。也许是因为它更加锻炼思维吧。

代码如下:

https://code.csdn.net/snippets/2289489

据说回爆栈?写了一个BFS的树链剖分……

 
 
评论