C++14(g++5.4) 解法, 执行用时: 57ms, 内存消耗: 4836K, 提交时间: 2019-09-11 20:31:45

//Author:XuHt
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100006;
int n, k, d[N], fa[N];
int Head[N], Edge[N<<1], Leng[N<<1], Next[N<<1], tot = 1;
bool v[N];

void add(int x, int y, int z) {
	Edge[++tot] = y;
	Leng[tot] = z;
	Next[tot] = Head[x];
	Head[x] = tot;
}

void dfs(int x, int &t) {
	v[x] = 1;
	for (int i = Head[x]; i; i = Next[i]) {
		int y = Edge[i], z = Leng[i];
		if (v[y]) continue;
		if ((d[y] = d[x] + z) >= d[t]) t = y;
		fa[y] = i;
		dfs(y, t);
	}
	v[x] = 0;
}

void dp(int x, int &t) {
	v[x] = 1;
	for (int i = Head[x]; i; i = Next[i]) {
		int y = Edge[i], z = Leng[i];
		if (v[y]) continue;
		dp(y, t);
		t = max(t, d[x] + d[y] + z);
		d[x] = max(d[x], d[y] + z);
	}
}

int main() {
	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		add(x, y, 1);
		add(y, x, 1);
	}
	int t = 1;
	dfs(1, t);
	d[t] = fa[t] = 0;
	int tt = t;
	dfs(t, tt);
	int ans = ((n - 1) << 1) - d[tt] + 1;
	if (k == 2) {
		while (fa[tt]) {
			Leng[fa[tt]] = Leng[fa[tt]^1] = -1;
			tt = Edge[fa[tt]^1];
		}
		tt = 0;
		memset(d, 0, sizeof(d));
		dp(t, tt);
		ans -= tt - 1;
	}
	cout << ans << endl;
	return 0;
}

C++(clang++11) 解法, 执行用时: 30ms, 内存消耗: 6172K, 提交时间: 2020-11-03 13:45:05

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=1e5+10;
struct bian{int y,gg,c;}b[M<<1];
int len=1,h[M],f[M][2],d[M];
void ins(int x,int y)
{
	b[++len].y=y;b[len].c=1;
	b[len].gg=h[x];h[x]=len;
}

int maxx=0,id;
void dfs(int x,int fa)
{
	for(int i=h[x];i;i=b[i].gg)
	{
		int y=b[i].y;
		if(y==fa)continue;
		d[y]=max(d[y],d[x]+b[i].c);
		if(d[y]>maxx)maxx=d[y],id=y;
		f[y][0]=x;f[y][1]=i;
		dfs(y,x);
		
	}
}

void dp(int x,int fa)
{
	for(int i=h[x];i;i=b[i].gg)
	{
		int y=b[i].y;
		if(y==fa)continue;
		dp(y,x);
		maxx=max(maxx,d[y]+d[x]+b[i].c);
		d[x]=max(d[x],d[y]+b[i].c);
	}
}

int main()
{
	int n,k;scanf("%d %d",&n,&k);
	for(int i=1;i<n;i++)
	{
		int x,y;scanf("%d %d",&x,&y);
		ins(x,y);ins(y,x);
	}
	dfs(1,-1);
	maxx=0;
	int st=id;
	memset(d,0,sizeof(d));
	dfs(st,0);
	f[st][0]=0;
	int ed=id,ans=((n-1)<<1)-maxx+1;
	if(k==2)
	{
		maxx=0;
		memset(d,0,sizeof(d));
		for(int i=ed;i;i=f[i][0])
			b[f[i][1]].c=b[f[i][1]^1].c=-1;
		dp(1,-1);
		ans-=maxx-1;
	}
	printf("%d\n",ans);
	return 0;
}