[Sdoi2014] 简单的树链剖分 以每个信仰应该建一个线段树，空间复杂度为 O(5×1010) O(5\times 10^{10}) 因此会爆空间，所以需要动态申请空间。 // whn6325689// Mr.Phoebe// http://blog.csdn.net/u013007900#include <algorithm>#include <

Description S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足 从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标