Bob有一棵$n$个点的有根树，其中$1$号点是根节点。Bob在每个点上涂了颜色，并且每个点上的颜色不同。
定义一条路径的权值是：这条路径上的点（包括起点和终点）共有多少种不同的颜色。
Bob可能会进行这几种操作：

1 x 把点$x$到根节点的路径上所有的点染上一种没有用过的新颜色。
2 x y 求$x$到$y$的路径的权值。
3 x 在以$x$为根的子树中选择一个点，使得这个点到根节点的路径权值最大，求最大权值。

Bob一共会进行$m$次操作。
$n,m leqslant 10^5$。

题解

这道题我是按着LCT的标签找的，然而看到这道题的时候满脑子都是树剖……根本看不出哪里要用LCT……个人觉得这题还是蛮巧妙的。
首先，如果我们把同一种颜色的点放到LCT的一棵Splay中去，那么可以发现，1操作恰好就是LCT的access操作了。
对于一个点，他到根节点的权值，也就是LCT中这个点到根节点的实链的条数。记$f[i]$表示$i$号节点到根的权值。由这个权值的性质，我们不难得到，对于两个点$x$与$y$，$x$到$y$的路径上的权值为$$f[x]+f[y]-2f[lca(x,y)]+1$$
于是第二个操作也解决了。
第三个操作，我们不难想到把dfs序抽出来，在线段树上查询即可。
最后我们还有一个问题，也就是$f$数组该如何维护。其实不难想到，在access操作把一条虚边变为实边，我们就把这条虚边对应的子树在线段树上$-1$，若将一条实边变为虚边，就把实边对应的子树在线段树上$+1$。于是问题得到了解决。
时间复杂度$O(nlog^2n)$。
代码实现上遇到了一些麻烦，这里讲一下我写的时候遇到的几个错误：

注意线段树初始化的值为这个点在原树上的深度+1。
还是原树与辅助树的问题，access操作时，当我们要对线段树上修改的时候，假如我们在Splay上要把实边$u$到$v$去掉，在线段树上修改的时候，并不是直接把$dfn[v]$到$dfn[v]+size[v]-1$这一段的答案$+1$，而应该找到$v$点所在的Splay中一直往左走，走到这棵Splay中深度最浅的点，再在线段树上进行修改。

代码

原文:大专栏 BZOJ4817 [SDOI2017]树点涂色