某岛

… : "…アッカリ~ン . .. . " .. .
August 3, 2012

SPOJ 10707. Count on a tree II

Brief description:

… 给定一棵树点权树,求树上两点之间的路径上,出现过多少种不同的权值。

Tags: 树上莫队算法、主席算法

Analysis:

… 主席算法太意识流了。。无限仰慕。。。 /$:Orz 。

先写莫队算法吧。。准备工作,开 A、B、C 三个数组。。。
。。A 数组离散掉点权,B 数组展开 dfs 序列,C 数组统计数字已经出现了多少次。。。
、先一次 dfs() 得到各种序列信息,对于每个点 u,。。。进入的时刻在 B 数组中标记 + A[u],离开的时刻标记 – A[u]。。
。。另外记录其进入的时刻 st[u]。。(这个量后面求 lca 的时候也要用到 。。。

。。这样得到了暴力算法。。。对于询问 (u, v),只要从 st[lca(u, v)] 时刻开始,分别扫描到 st[u] 和 st[v] 的位置,
注意 lca 的位置只取一次。。

先把至此为止的部分调对。。之后开始调整询问顺序。。。
。。我一开始的策略是根据 lca 进行分组。。。不过这个退化的太厉害了。。
(。。貌似是组与组之间的转移没处理好。。不过这样对于一个询问。。就有三个指针位置。。莫非要跑三维曼哈顿最小生成树?。。。

。。然后我就 yy 了一下。。因为 lca 的位置依赖于 u, v。。。Orz。。
。。。这样就只对后面的两个轴跑莫队算法。。复杂度虽然不太清楚。。不过好像能过的样子。。。

树上莫队算法。。(30s+ 。。。

External link:

http://www.spoj.pl/problems/COT2/
http://seter.is-programmer.com/posts/32857.html