如果只有一种颜色,显然 $LCT$
多种颜色,发现颜色不多,所以对每一种颜色建 $LCT$
编号 $c$ 的颜色的第 $i$ 个节点在 $LCT$ 中编号 $c*n+i$
改颜色的时候有一堆细节,具体来讲
用 $map$ 来判断两点之间是否有边并记录边的颜色,注意边 $(x,y)$ 和 $(y,x)$ 是等价的
记录 $cnt[i][c]$ 维护节点 $i$ 颜色 $c$ 的边数
用 $findroot$ 判断两点之间是否已经有路径
注意改颜色的时候颜色可能不变!一定要特判!
注意边的颜色从 $0$ 开始
#include #include #include #include #include #include #include #include