做题时间：2022.10.10
\(【题目描述】\)
给定一棵 \(N(N\leq 10^5)\) 个点的树，现在可以在这些点之间建立 \(k(1\leq k\leq 2)\) 条边，使得从编号1的点便利一遍所有的边后返回点1所走过的距离最短，问这个最短距离。
\(【输入格式】\)
第一行两个整数 \(N,K\) 表示点的数量和要建立的边的数量
接下来 \(N-1\) 行每行两个整数 \((u,v)\) 表示村庄 \(u\) 和 \(v\) 之间有一条连边
\(【输出格式】\)
一行一个整数表示答案
\(【考点】\)
树的直径
\(【做法】\)
考虑建立的边在两个点 \((u,v)\) 上 ，在建立之前，走到 \(u\) 之后必须返回根节点，再走到 \(v\)，建立之后则可以直接走 \((u,v)\)，因此节省树上简单路径 \(u\rightarrow v\) 的距离，因此当 \(k=1\) 时，肯定将 \(u,v\) 建立在直径的两端，设直径长度为 \(l\)，则答案为 \(2(n-1)-l-1\) 。当 \(k=2\) 时，即将两条边设在最长的和次长的两条路径上即可，求次长路径只需将求出的一条直径的边权改成 \(-1\) 后再求一边直径即可。设最长路径长为 \(l\)，次长路径长为 \(p\)，则答案为 \(2(n-1)-l-p\)
寻找直径上的点我用了dfs序区间判断哪些点是端点的祖先。
\(【代码】\)
#include<cstdio>
#include<iomanip>
#include<cstring>
using namespace std;
const int N=1e5+50;
struct edge{
int to,val,nxt;
}a[N<<1];
int pt[N],tot;
int head[N],num1[N],num2[N],cnt,n,m,st,ed;
int maxn[N],sec[N],ans,l[N],r[N],idx,k,root;
void add(int u,int v,int w)
{
cnt++;
a[cnt].to=v;
a[cnt].val=w;
a[cnt].nxt=head[u];
head[u]=cnt;
}
void dfs(int u,int fa)
{
l[u]=++idx;
num1[u]=num2[u]=u;
for(int i=head[u];i;i=a[i].nxt){
int v=a[i].to;
if(v!=fa){
dfs(v,u);
if(maxn[v]+a[i].val>=maxn[u]){
num2[u]=num1[u],num1[u]=num1[v];
sec[u]=maxn[u],maxn[u]=maxn[v]+a[i].val;
}
else{
if(maxn[v]+a[i].val>sec[u]){
sec[u]=maxn[v]+a[i].val;
num2[u]=num1[v];
}
}
}
}
if(maxn[u]+sec[u]+1>ans){
ans=maxn[u]+sec[u]+1;
st=num1[u],ed=num2[u];
root=u;
}
r[u]=++idx;
}
void dfs2(int u,int fa)
{
for(int i=head[u];i;i=a[i].nxt){
int v=a[i].to;
if(v!=fa&&((l[v]<=l[st]&&r[v]>=r[st])||(l[v]<=l[ed]&&r[v]>=r[ed]))){
//若v是直径端点st或ed的祖先，则v一定是直径上的点
dfs2(v,u);
pt[++tot]=i;
}
}
}
void init()
{
memset(maxn,0,sizeof maxn);
memset(sec,0,sizeof sec);
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v,1),add(v,u,1);
}
dfs(1,0);
if(k==1){
printf("%d\n",2*n-ans);
return 0;
}
dfs2(root,0);
int pre=ans;
ans=0;
for(int i=1;i<=tot;i++) a[pt[i]].val=-1;
init();
dfs(1,0);
printf("%d\n",2*n-ans-pre+2);
return 0;
}