SPOJ Count On Tree II

题目链接

题意

给出一棵大小为 $n$ 的树以及树上每个点的颜色,并且给出 $m$ 个询问 $(u,v)$ ,对每个询问求出 $u$ 到 $v$ 这条链上有多少不同的颜色
$n\leq 40000, m\leq 100000$

题解

第一次打树上莫队这东西
首先对于一条链的情况直接用普通莫队就可以解决
对于一棵树的情况,我们考虑如何将它转化为序列问题
可以使用欧拉序,我们将对每个点访问开始和结束时分别塞进序列里,就做出了欧拉序,例如样例
选区_155.png
对应的欧拉序就是
$\texttt{1 4 8 8 4 3 7 7 6 6 5 5 3 2 2 1}$ 继续阅读