save_code @ 2018-06-14 09:33:06

不过维护参数很麻烦
第二问的 答案 等于 总数 减去 枚举 每个颜色， 这条链上所有不包含 这个颜色的和

我们可以 dp[id]记录 id 到根节点 不满足条件的答案 （也就是 相同两个颜色 之间距离减 1的组合数和）

A,B 这条链的 反面结果 就等于 dp[lca]+ 每种 颜色 三个关键点的 情况 比如 a,b,c 就是(dist[b]-dist[a]-1)*(dist[c]-dist[a]-1)

a表示 改颜色 在 A到lca之间 离lca最近的 点，b表示 该颜色在 B到lca之间 离lca最近的点,c表示 lca到根节点 之间离 lca最近的点，
然后 莫队算法维护这三个点 以及 一系列（一坨)参数

反正 目测应该是可以实现的，只不过 很麻烦，很纠结。。

复杂度n*sqrtn

save_code @ 2018-06-14 09:46:00

还有主要麻烦点 在于 A到LCA 之间 不存在 某种颜色和B到LCA之间 不存在某种颜色，要维护一个 二元二次多项式， x,y 分别对应查询的 dist[a] 和dist[b]

save_code @ 2018-06-14 16:17:19

我觉得 用我的对颜色分块 实现起来 更简单一些啊 虽然多个根号log

nzhtl1477 @ 2018-06-17 14:27:20

orz 600行

nzhtl1477 @ 2018-06-17 17:07:52

肯定
（话说您的代码一直都很长耶）

save_code @ 2018-06-17 17:10:27

那道题 论文的方法没有见过啊。。。。自己自创解法

Claris @ 2018-06-18 15:09:43

标算是利用数据随机性O(nlogn)做的。