题面 P4606 [SDOI2018]战略游戏 Solution 圆方树上圆方果， 圆方树下你和我。 圆方树前建虚树， 欢乐多又多。 好吧，我们来说正题。 这题就比较强。根据常识，如果我们爆掉的点能影响这个图的连通性，那么，这个点一定是割点。 因此，我们要先对原图做Tarjan求点双。接下来，我们考虑用圆方树来解决一个问题。 我们先考虑暴力怎么做，我们先对原图求出圆方树。 接下来，我们...

题面 P2617 Dynamic Rankings Solution 这题需要一个比较妙的操作。 首先，我们阅读题面，发现题目要求我们处理区间K大带单点修改的问题。我们考虑用整体二分来解决这个问题。 总所周知，**整体二分中的修改只能以“添加”的形式进行，而不能以“覆盖”的方式进行。但这里，我们修改一个位置的数之后，新的数会把原来的数覆盖掉。**如果我们不能处理好这个问题，整体二分一定会错...

什么是GUIDE GUIDE(GAIT Universal IDE)是由北航GAIT研究组开发的、专门为NOI选手设计的轻型集成开发环境。GUIDE具有跨平台、操作简单、支持C/C++/Pascal三种语言和单文件编译调试等优点。经过近一年的试用和修改之后，GUIDE 1.0.1版目前正式发布。 ——www.noi.cn 换句话来说，GUIDE是一个NOI官方指定的，在NOI Linux...

题面 P3233 [HNOI2014]世界树 Solution 这是一道虚树妙题。 我们不妨先考虑一下每一次$O(n)$计算的暴力怎么做。 $O(n\cdot m)$的暴力肥肠简单，我们只需要做两遍dfs。考虑设$f[i]$表示离$i$最近的聚居地是什么，$MIN[i]$表示$i$到最近的聚居地的距离。我们第一遍dfs先找出$i$到它子树内的聚居地的最小距离，之后再做一遍dfs来找$i$往...

题面 P4297 [NOI2006]网络收费 Solution 这题喵啊。 首先，我们会发现统计两个点互相的贡献是一个极其困难的问题。 但是，仔细观察那张收费表格后会发现，我们可以重新定义一下这个收费：我们假设路由器节点的颜色为叶子中数目较多的颜色，当一个叶子结点颜色与路由器节点颜色相同的时候不收钱，否则收一份钱。我们可以惊讶的发现，这样做之后我们的新收费做法就与原来题目要求的重合了，而且...

题面 4438 [HNOI/AHOI2018]道路 Solution 这是一道树形DP妙题。 平时，我们设计树形DP的状态一般都是以子树为基础来设计的。很不幸的是，这题因为那个蜜汁柿子无法化简，导致了极其严重的后效性。因此，我们这里并不能以子树为基础来设计状态了。 这题妙就妙在这个状态设计。这题我们考虑以链为基础来设计状态。 设$f[i][j][k]$表示从根节点到达第$i$个点，一路上经...

题面 P3332 [ZJOI2013]K大数查询 Solution 这是一道不辣么模板的整体二分题。 首先，我们先来假设一下只有一个询问应该怎么搞。 考虑这样做：我们先二分一个答案，修改中，如果所要修改的数大于mid，则在这段区间中每个数加上1。否则什么都不做。这样一来，最后我们只需要看一下询问的区间的区间和是否大于$K$即可。 接下来，我们考虑如何把所有询问一起来二分。 同样还是二分一个...

题面 P3527 [POI2011]MET-Meteors Solution 我是一直奉行坚决不写树状数组只写线段树理论的，直到这题… 这题是一道整体二分的模板题。 首先，我们考虑只有一个国家的情况。这不SB问题么 我们可以二分一个答案，然后我们用线段树暴力模拟，暴力Check,复杂度$O(mlogn)$。 显然，如果我们每一个国家都这么搞一轮，复杂度达到了惊人的$O(n\cdot m l...

题面 P3810 【模板】三维偏序（陌上花开） Solution 这是一道CDQ分治的模板题。 题目要我们求的是$(a,b,c)$这样的三维“顺序对”的数量。 考虑我们把所有的数按照以$a$为第一关键字，以$b$为第二关键字，以$c$为第三关键字来排序。 这样子，我们就可以保证有可能与某个数形成“顺序对”的数一定在它的左边。 我们都知道，归并排序能用来求逆序对的数量，在这里，也能用类似的方...

题面 4025: 二分图 Solution 这种每条边出现在一段区间的题，我们可以先考虑使用线段树分治来搞。 这题我们考虑离线下来搞。离线之后，我们会发现，某条边会在某些询问区间中出现。 考虑以询问的编号为下标建线段树，我们把每一条边出现的时间段全部加到线段树里面去。 接下来，我们考虑如何维护一个图是否为二分图的问题。我们知道，一个图是二分图当且仅当这个图上所有的环的长度(点的个数)均为偶...