poj1751题目链接

题意：一开始有一些边，然后添加一些边，使得代价之和最小。

思路：先把给定的边merge掉。。然后计算其余可以添加的边。。。接下来就是最小生成树。。。

hdu4607题目链接 题意：给出一棵树。。。边权都为1. m个查询。。每个查询给一个k,表示只访问k个点。。。问每次的最小路径和是多少。。。 思路：我们发现。。会使路径和变大的一个不利因素是折返。。也就是访问某景点后。。必须要回去才能继续前进。。这样的距离是2倍。。那为了使得路径和尽可能小。。我们就尽量不要访问这样的点。。。而不是这样的点一定在直径上。。。以及我们还发现。。。不在直径上的点。。 。。不管深度如何（深度的意思是说，与和该点最近的直径上的点的距离），距离的贡献是一样的。。都是2倍。。所以我们可以推出一个公式。。。如果树的直径是d,那么k<=d+1的时候，答案为k-1,否则答案为d+(k-d-1)*2。。。

poj3310 题目链接

题意：给出一个无向图。。。问是否满足。。联通，并且无环，并且能找到一条路径，图中所有的顶点要么在这条路径上，要么与这条路径上的顶点相邻。

poj1679

题意：问最小生成树是否唯一。。

思路：求一下次小生成树。。。如果无解，或者次小生成树的权值之和和最小生成树的权值之和不同，那么唯一，否则不唯一。1A

hdu4514

题意：给出一个无向图。。问是否有环。。。有的话输出YES。。如果没有环的话。。输出最长路径。。

思路：无向图判环并查集就好。。。关于最长路径这里。。一开始以为就是树的直径。。。

hdu2196

题意：给出一棵树。。。求距离每个点的最远距离是多少。。。

思路：最远距离什么的。。能想到树的直径。。。但是有什么关系呢？ 我们在求树的直径的时候。。。直径的两个端点是可以知道的。。。如果再从两个端点分别做两次bfs。。。每个点取两个距离的较大值就是答案。。。。？

poj2631 题意：一棵树中求两个点的最远距离。。。 思路：就是求树的直径。。。裸体。。。。1A

/* ***********************************************
Author :111qqz
Created Time :2016年07月12日 星期二 13时03分39秒
File Name :code/poj/2631.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream> …

poj1985 题意：求树上两点的最长距离。。。也就是传说中的树的直径。。。

思路： **两遍BFS :先任选一个起点BFS找到最长路的终点，再从终点进行BFS，则第二次BFS找到的最长路即为树的直径；** 原理: 设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点 证明: 1) 如果u 是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾) 2) 如果u不是直径上的点，则u到v必然于树的直径相交(反证),那么交点到v 必然就是直径的后半段了 所以v一定是直径的一个端点，所以从v进行BFS得到的一定是直径长度

参考博客

  * <del>树的直径，次小生成树（）</del>
  * <del>最小生成树（拒绝划水，推一波难题）</del>
  * 《编程珠玑》
  * 博弈论。。全部搞定。。。
  * dp。。。基础dp，区间dp，树形dp，概率dp。。至少搞定这些。。（从头开始学dp2333）
  * <del>markdown语法。。还是有必要学一下的。</del>
  * <del>multi 2016 #4 1006 -> SA SA? SA SA!</del>
  * <del>单调栈？单调栈？单调栈单调栈！ （一堆题卡在这里 …

URAL1416 题意：次小生成树模板题

思路：用Kruskal求最小生成树，标记用过的边。求次小生成树时，依次枚举用过的边，将其去除后再求最小生成树，得出所有情况下的最小的生成树就是次小的生成树。复杂度o(m2)。。。貌似有其他优化。。。