---

Description:一棵树，添加k条边使得遍历所有的点的总代价最小，其中1<=k<=2;

不建道路，路线总长度2*（n-1）；

当k等于1，此时的最优解无疑是将边加到直径两端；那么答案就是2*(n-1)-d+1；其实考虑k=2时，对于一棵树，我们加边会形成一个环，加两条边形成两个环，我们就要考虑这两个环的关系了；

1.两个环上的边不重叠；我们只需要再次找一下最长链，忽略直径哈，答案减小；

2.两个环上的边有重叠部分；我们将其作为加1条边的请况，那么两个环重叠的不会将不会被经过，重叠部分则需要经过两次，所以我们需要让车在适当时候重新经过这些边，并且返回，最终的结果是我们让两个环上的重叠的边经过了两次；

所以：

1、求树的直径L1，将L1上的边权取反，变为-1；
2、再求树的直径L2，答案即为2(n−1)−L1+1−L2+1=2∗n−L1−L2；

如果L2这条直径包含L1取反的部分，就相当于重叠，减掉（L1-1），重叠的边经过了一次，减掉（L2-1），把重叠部分加回来，变为需要经过两次；

时间复杂度O（N）；对于找树的直径，有bfs(dfs)和dp两种做法:但是bfs的做法遇到负权好像不太行，但是dp可以，但是dp好像只可以求个直径；

bfs:

int bfs(int x){//返回终点标号
	queue<int>q;
	memset(d, 0x3f3f3f3f, sizeof d);
	memset(pre, 0, sizeof pre);
	q.push(x);
	d[x] = 0; pre[x] = 0;
	while (q.size()){//bfs将所有d[]更新，并将前驱节点存入pre[]
		int now = q.front();
		q.pop();
		for (int i = h[now]; i; i = next_pos[i]){
			int j = e[i];
			if (d[j] == 0x3f3f3f3f){//只要没有更新就更新
				d[j] = d[now] + w[i];
				pre[j] = now;//将父节点存起来
	...