题目：传送门；
题目大意：一棵树，添加k条边使得遍历所有的点的总代价最小，其中1<=k<=2;
首先呢：不建道路，路线总长度2*（n-1）；
我们分析当k等于1，此时的最优解无疑是将边加到直径两端；那么答案就是2*(n-1)-d+1;这样你会得到30分；
其实我们考虑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好像只可以求个直径；
#include<bits/stdc++.h> using namespace std; #define N 500010 template<typename T>inline void read(T &x) { x=0;T f=1,ch=getchar(); while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} x*=f; } struct gg { int y,next,v; }a[N<<1]; int lin[N],vis[N],dis[N],dis1[N],father[N],tot=1,n,k,ans,d,x1,x2; inline void add(int x,int y,int z) { a[++tot].next=lin[x]; a[tot].y=y; a[tot].v=z; lin[x]=tot; } queue<int> q; inline int bfs(int s) { memset(vis,0,sizeof(vis)); int point=s; q.push(s); dis[s]=0;vis[s]=1; father[s]=0; while(!q.empty()) { int x=q.front();q.pop(); for(int i=lin[x];i;i=a[i].next) { int y=a[i].y; if(!vis[y]) { vis[y]=1;q.push(y); dis[y]=dis[x]+a[i].v; father[y]=x; if(dis[point]<dis[y]) point=y; } } } return point; } inline void dp(int u) { int maxn=0; for (int i=lin[u];i;i=a[i].next) { int v=a[i].y; if (v!=father[u]) { dp(v); ans=max(ans,maxn+dis1[v]+a[i].v); maxn=max(maxn,dis1[v]+a[i].v); } } ans=max(ans,maxn); dis1[u]=maxn; } inline void get() { x1=bfs(1); x2=bfs(x1); bfs(1); memset(vis,0,sizeof(vis)); if(dis[x1]<dis[x2]) swap(x1,x2); vis[x1]=vis[x2]=1; while(dis[x1]>dis[x2]) { x1=father[x1]; vis[x1]=1; ++d; } while (x1!=x2) { x1=father[x1]; x2=father[x2]; vis[x1]=vis[x2]=1; d+=2; } } inline void tab(int x) { for(int i=lin[x];i;i=a[i].next) { int y=a[i].y; if(y!=father[x]) { if(vis[x]&&vis[y]) { a[i].v=a[i^1].v=-1; } tab(y); } } } int main() { //freopen("data.in","r",stdin); //freopen("data.ans","w",stdout); read(n);read(k); int x,y; for(int i=1;i<n;i++) { read(x);read(y); add(x,y,1);add(y,x,1); } get(); if(k==1) { printf("%d ",2*(n-1)-d+1); exit(0); } if(d==n-1) { printf("%d ",n+1); exit(0); } else { tab(1); dp(1); printf("%d ",2*n-ans-d); } return 0; }