传送门 这道题其实就是P4185 [USACO18JAN]MooTube和P3224 [HNOI2012]永无乡的结合。 看到第kkk高，就要想到主席树，但是考虑到题目条件：只经过困难值小于等于x的路径，于是考虑离线操作，把询问和边按照边权从小到大排序，来了一个边权为xxx的询问，只要把$ \le x$的边全部连上，同时合并两个连通块所代表的主席树即可。 代码： 12345678910111...

BZOJ GDOI 对于每种颜色开一棵线段树，比如说对于颜色序列1 2 2 3 3 2\text {1 2 2 3 3 2}1 2 2 3 3 2，它的线段树开出来是这样的： 因为两种颜色搞在一起后，没有任何操作能把他们分开，不妨把替换视为合并。 比如把333替换成222，就是把333合并到222。 考虑如何pushup\rm pushuppushup，只要维护区间左右端点值(0/1)(...