今天做cf交互题的时候遇到了括号序，顺便就来学(fu)习(xi)了一波树上莫队。

---

有一种神奇的东西叫做括号序，即当访问到i的时候加入序列，然后离开i的时候再加入序列。

eg:1-->2,2-->3,2--4,那么括号序列 1 2 3 3 4 4 2 1

这样我们成功将树映射到了序列上，一个点有st[x]也有ed[x]，以该题为例，我们统计颜色(x,y)时候分类

1. lca(x,y) == x 那么统计st[x]到st[y]之间的只出现过一次的点(出现两次无贡献）的贡献。

2.lca(x,y) != x 那么由于它们之间路线不在各自子树内那么统计ed[x]到st[y]的贡献。但是这样没有计算LCA的贡献，单独加上。

 

没有代码，，时间问题，云AC