P2486
P2486 [SDOI2011] 染色
题目描述 给定一棵 \(n\) 个节点的无根树,共有 \(m\) 个操作,操作分为两种: 将节点 \(a\) 到节点 \(b\) 的路径上的所有点(包括 \(a\) 和 \(b\))都染成颜色 \(c\)。 询问节点 \(a\) 到节点 \(b\) 的路径上的颜色段数量。 颜色段的定义是极长的连续相 ......
解题报告P2486 [SDOI2011] 染色
P2486 [SDOI2011] 染色 题目链接 分两段,最后靠同一条重链合 树剖加线段树,典中典。 这题的线段树维护比较新颖。 线段树中维护这个区间左右端点的颜色和颜色段数量。 建树和查询和修改时要判断左区间的右端点和右区间的左端点是否颜色相同。 如果不相同,直接将段数相加,否则减一。 然后就是查 ......