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。。
。。。这样就只对后面的两个轴跑莫队算法。。复杂度虽然不太清楚。。不过好像能过的样子。。。
External link:
http://www.spoj.pl/problems/COT2/
http://seter.is-programmer.com/posts/32857.html
