题目：；

题目大意：一棵树，添加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
      
       using namespace std;#define N 500010template
       
        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
        
          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[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