这个题倒是不难，但是我当时对于题目的理解导致写出来很复杂，所以记一下踩的坑。其实就是最短路树的应用，我的想法是先删掉不在树上的边，然后对于树上的边先删除连叶子的边，以此类推。这样写倒是没有错也可以过。
但是！这个题题面里说的是最多k个，所以其实根本不用考虑去掉非树边什么的，假如k>n-1的话只输出n-1条树边也是对的！这就省了好多代码了。其次，根本不用使用拓扑排序那样的处理过程（就是先去掉叶子这种），因为想一下dijkstra的过程就可以发现，每次从优先队列中取出来一个节点后，这个节点的前驱最短路其实已经确定了，只要在这时候把其前驱记录下来，根据dijkstra的每一步往外扩展一步的操作，按照这个顺序搞下去最后的记录表中的顺序其实就是拓扑序。。。。依次输出即可。 继续阅读“[CF][图论][最短路树] codeforces 1076D Edge Deletion”
http://codeforces.com/contest/1061/problem/D
嗯。。。又是这种一维的区间最优化策略问题了。。。似乎已经感觉到了套路。。。（赛场上贪心有感觉就直接上了
这种题一般是先排序（以左端点或者右端点）搞出来一个顺序，然后在这个顺序的基础上逐个考虑。考察到某一段时候一般需要做决策，然后这时候可以根据具体题目来看是贪心决策还是dp，如果直觉是贪心（毕竟真正证明有时候确实不好弄），那一般决策都跟满足条件的极端值有关，比如在这里就是如果存在能合并的点（如果连最基本的两段合并后小于各买一台电视机都不满足那一定不能合并），那么一定是和这段左边最靠近他的一个点合并。具体证明可以分情况讨论，一般真的证明的时候就是得考虑，如果不这么合并，计算出来的结果和原来的结果对比，一般要考虑之后的seg的影响，在考虑的时候可以分情况讨论（反正我一般有直觉就上233
然后在实现的时候，有时候没有头绪可以想想STL！（想起了ccpc网络赛被set支配的恐惧），这个东西有时候真的有妙用，它既保持了单调的性质（可以用来贪心）又有着动态维护的特性（贪心的动态调整）。
wa点又是精度，嗯万年精度，这次竟然LL也炸了，而且是因为add的两个参数本身可以达到LL，然后一加给爆了。。。。我去
首先可以确定要分一个trouble，那一定是等分，这一点可以从公式化简得到。
所以难的问题是，给每一个trouble分几个人。当没有什么做法/头绪的时候，想一想贪心递推的操作（贪心是因为这个题数据量不应该是dp），大问题是否可以从小问题转化过来，每次多一个人的时候，这个人应该放到哪儿？可以试着遍历每一个trouble看看放在哪里会使得变小最多，但是这样是M^2的做法，但是这时候考虑“哪里小的最多”这个条件，以及，+1之后哪里变小的最多是完全取决于trouble的数值和他当前已经有的人的，所以可以用一个优先队列来存储“哪里变小的最多”这个信息！这样的话就是M^logM的算法了，可以通过本题。
自己当时为什么想挫了？主要是一开始想的把一个划分之后可以看成两个新的数，但是事实并非如此，新分出来的和原来的是不等价的，同一个trouble分出来的可以互相组合，但是不同德trouble之间不能组合，所以这种思路可以否定。所以其实每次都要考虑所有的trouble，取变小最多的那个，想到这里又觉得是M^2的算法，又没有继续，但是这时候思路已经是对的了，就可以考虑可以用什么优化，尤其是这种最值/顺序之类的问题，可以多考虑数据结构优化。
评论区大佬：嗯这个题贪心很明显啦然后nlogn方法也有很多种
http://codeforces.com/contest/980/problem/E
要使得去掉一些点之后剩下的仍然是一棵树，那么去掉的一定是叶子或者某条路上的缩点后相当于叶子的子图。。描述有点困难自行yy。。然后如何选择去掉的点？可以发现，如果i<j，那么去掉j一定不如去掉小于j的所有数，因为2^j=2^(j-1)+2^(j-2)+2^(j-3)+…..+2+1，所以贪心策略就是能不去掉大的就不去，所以要从n-1开始一个一个找（由于k<n所以节点n一定不会被去掉），怎么确定一个点是否能被保留下来，只要确定这个点到最近的保留下来的点的距离小到可以满足去掉k个的要求（想一下，如果这个点离最近的保留点太远了，远到了如果保留这个就没法保证能去掉k个点了，那就肯定不能留了），要保留这个点一定也要保留从这个点往上回溯所有的点，然后就会发现在以root为根的树上，这个01标志是连续的分布的，也就是说有一段1111然后一段000，这样的话就可以二分求分界点，而树上的二分就是lca里的倍增算法了，用倍增法查找就可以在logn时间内找到分界点，找到之后判断是否满足要求，如果满足则把分界点到当前点都标记上保留（话说这样logn不就退化了吗。。。）
wa点是距离的处理和树上倍增往前跳的时候把cur写成了i。。。
比赛结束智商上线系列
昨天的时候看C没整明白然后来看D，没想出来构造方法又回去卡C结果最后都没出呵呵呵，今早起来写了几个样例，组合了下就发现了规律：每次找到left最大的那个人和right最大的那个人，如果不是同一个人就合并中间left和right重合部分，ans加上这一部分（ans+=max(maxleft,maxright)）然后把这俩人重合的部分消去合并成一个新人放回集合里；如果是同一个人那就自己一个人一个圈子就好了。
感性理解的话就是要尽可能的让长的段之间有重复，重复就可以节省椅子，而始终都找最长的left和right就能保证这一要求。
wa点：multiset中如果两个元素它们定义<运算符的那个信息相同他就认为是相同的，而erase的时候会把所有相同的都erase掉，所以为了区别不同的人加上了一个id。。。很神奇吧。。
http://codeforces.com/contest/1041/problem/E
比赛完5min想到了ac做法emmmm
并没有看懂官方题解，NO的判别其实很简单，只要有b不是n的情况就NO，因为不管怎么分都一定会有一个n。YES的情况怎么构造？我自己的做法是把n作为根节点，把条件排序后从小到大考虑：如果一个点出现了一次，那么就连一条从根节点到这个点的边，并且把这个点标记为用过的；如果出现了多次，那么就到前面找没有标记过的点找一个最小的插到当前点和他的父节点之间，并且把找到的点也标记为用过的。
所以为什么是正确的？首先按照a排序后可以发现如果一个数字重复出现了那么一定是从第ai个往前重复，如1 3 3 4，这个重复的3一定是从第3个往前延申，按照我的构造方法，如果不是这样那就不可能满足要求，因为3和5之间的路上的节点一定是全是小于3的数字，而且以3为根的子树我这里直接让他为空。这样的话总可以在前面找到足够数量的数字来插入到3的这一条链上（忽然感觉说不清楚了但是这么构造一定是对的emmmmm
wa的话感觉可能是当时很饿然后树上的插入操作和标记都写错n次，神奇的是每次都能通过前30个test然后被3x刷掉。。
先说结论：构造的方法就是以任意一个点开始dfs，对于dfs到的点，把他的颜色设置为没有在与他所有的相邻的已经被染过色的节点的颜色的集合中出现过的最小值，比如和它相邻有4个点，其中3个分别为1，3，3，另一个未染色，那么就把当前的颜色设置为2。
这个做法，网上并没有找到一个说得过去的证明，我自己也无法严格证明贪心过程的正确性，也没有找到官方题解，就是很玄学。而且，同样的贪心过程，如果先对一个点先dfs再染色，也就是根据子孙节点的颜色修改当前的颜色，就会出现某个节点大于k的情况（虽然仍然是保证了不同点之间不同染色），但是如果先染色再dfs，也就是先处理好搜索过的节点，根据祖先节点修改当前的节点，就能保证通过所有数据。
继续阅读“[思维][贪心] UVa1613 K-Graph Oddity”
从后往前，如果遇到下雨的天气就存进优先队列里，如果遇到不下雨的天气，优先解决离当前位置最近的湖，用vis记录一个湖是否有危险，如果遇到一个下雨天这个湖已经有危险了那么就输出NO，否则标记为有危险，如果是不下雨的天有则把有危险的（队列中的）前一个最大的湖去掉。到最后如果队列非空则也输出NO，说明有的湖的危险没有解决。
连续做的又一道预处理+贪心的题目，一开始因为复杂度的原因一直没有下手，看了官方题解才意识到复杂度是nlogn，因为调和级数求和是logn。。。
贪心策略就是每次都选择能覆盖到的范围内的最右边的非block的点，如果这个点等于原来的出发点就直接return -1，因为说明不可行。这时候我们需要预处理出来每个点对应的它左边离他最近的那个非block的点（也有可能是他自己），当然这个预处理就很简单了。主要的思考难度在于没想到可以这么预处理，其次是复杂度的分析没有到位。
错误的点的话是对题意的理解：这里要求覆盖整条线段，而不仅仅是覆盖整点，但是放灯却只能在0到n-1的整点上放。。。第二个错误是如果0处禁止放的话那直接就是输出-1了，原来的算法在这里会失效，因为那个总是多考虑一步，而没有考虑出发点是不是合法的。
