思路全在论文里，实现的话费了点功夫。。感觉写这种复杂一点的题，最好还是先把需要用到的变量都写出来，需要的操作都列出来，不然反复修改会浪费很多时间。
需要注意的错误只发现了一个就是在枚举加度的时候可能会出现没边可删的情况（我也不知道为什么），然后这时候我的代码就开始跑环。。因为每次都会新加入一条边，不删边的话必定在树上形成环。后来的策略是一旦当前的操作不再使得生成树变小，那就直接break，因为显然他之后也不会再变小，而且可能之后会出现跑环，而这之前我的代码都是正确的，这样既可以剪枝又可以避免坑。。。 继续阅读“[生成树][treeDP][图论] 最小度限制生成树 POJ1639 Picnic Planning”
这个题确实是领悟到了不少东西，lca倍增的思想和用途，思维方法，构建生成树的逻辑，严格次小的要求。发现图论很重要的一个东西就是存储用的数据结构，我不怎么会写前向星于是就很难受了。。就这个题而言是要先求MST，再对MST做LCA，那么就会有两个图，一个是原始的用来求MST，另一个用来求LCA，第二个就是MST这个树本身。所以建了俩图，第二个图是在Kruskal的过程中建立的，与此同时还要记录下来不在MST上的边，以便之后的枚举操作。另外一个需要注意的点就是要求是严格次小，所以的就需要保存一个第二大这么一个数，这个又有很多情况，不同树上区间合并的时候根据两个区间最大的数的关系来处理。
错误的话，1 求LCA的时候应该swap 使得较深的为y，这里写错了 2 数组容量开错，这个今天错了几次，主要是没看清m和n，而且总是蜜汁把m写成n。。 3 数组下标写错（为什么经常做这种蠢事？？？？ 4 跟LL比较大小却初始化为1<<29，，显然不够，改成1<<60就过了，也是最后一个错误
继续阅读“[图论][生成树扩展][LCA] bzoj1977 次小生成树模板题”
