USACO的最新的月赛出来了。。本菜去被题虐了。。
我感觉第一题是将环拆成2份。。然后将每条线段。。如果跨越环的话，就只有一份。否则有两份。。然后去掉被包含的线段。。那么题目就变成了在这个2*C长 的大线段上取一些线段时其并集为线段切长度>=C。。那么就好办了。。维护两个指针扫描过去就可以了。。当左边界递增的时候右边界也是递增的。。
第二题好猥琐啊。。直接拆点构图然后bfs？似乎可以但是节点会有重合。。也就是说会有长度为0的边。。那么怎么半呢？我的办法是。。bfs不是维护一个 队列嘛。。我改成一个双端队列。。然后遇到为0的边加在头部，否则加在尾部。。就OK了。。这道题写的我脑子都大了。。。写了我3KB。。神牛一定有更简 单的办法。。我太菜了。。
第三题感觉最简单。。构造树的先序数列。。然后用一个线段树维护每个点到根节点的染色点的个数（就是有Cow的点的个数）。。然后那么一个点染色之后只影 响它的子孙的哪一段区间。。只要用标准的线段树就OK了。。
比赛嘛。。代码就不发了。。