题目大意

给出一棵有$n$个节点的有根树，然后新建$k$条边，边权全都是$1$

询问此时从根节点出发遍历回到根节点的最短路程

数据范围

$3\leqslant n\leqslant 10^5,1\leqslant k\leqslant 2$

题解

对于原图来说，所求的最短路程就是$2\times (n-1)$，因为树的每条边在遍历时都会不可避免地经过两次

新建一条边是为了减少原图一个边集中每条边经过的次数，使得这个边集中每条边在遍历时只经过一次

则问题就转化为如何使得这个边集最优，理所当然的就是树的直径$(diameter1)$

所以当$k=1$时，$ans=2\times (n-1)-diameter1+1$

当$k=2$时，我们就可以在第一种情况下得到的新图中再选择一个边集，再次优化最短路程

所以我们把第一次求的树的直径中每条边边权改为$-1$，再跑一边树的直径$(diameter2)$

所以当$k=2$时，$ans=2\times (n-1)-diameter1+1-diameter2+1$

最后，围观大神系列

程序

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define goedge(i,x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n,k,s,dia,ans,et=1;
struct edge{int to,next,c;}e[200500];
int last[100500],path1[100500],path2[100500];
inline void addedge(int u,int v,int c){
    e[++et]=(edge){v,last[u],c};last[u]=et;
    e[++et]=(edge){u,last[v],c};last[v]=et;
}

int dfs(int x,int fa){
    int mx1=0,mx2=0;
    goedge(i,x){
        if (e[i].to==fa) continue;
        int sum=dfs(e[i].to,x)+e[i].c;
        if (sum>mx1) mx2=mx1,path2[x]=path1[x],mx1=sum,path1[x]=i;
        else if (sum>mx2) mx2=sum,path2[x]=i;
    }
    if (dia<mx1+mx2) dia=mx1+mx2,s=x;
    return mx1;
}

int main(){
    n=read(),k=read();ans=(n-1)<<1;
    For(i,1,n-1){
        int x=read(),y=read();
        addedge(x,y,1);
    }
    dfs(1,0);ans-=dia-1;
    if (k==2){
        dia=0;
        for(int i=path1[s];i;i=path1[e[i].to]) e[i].c=e[i^1].c=-1;
        for(int i=path2[s];i;i=path1[e[i].to]) e[i].c=e[i^1].c=-1;
        memset(path1,0,sizeof(path1));memset(path2,0,sizeof(path2));
        dfs(1,0);ans-=dia-1;
    }
    printf("%d\n",ans);
    return 0;
}