题目
这题貌似是我接触的第一道APIO的题，当时完全不知道怎么做呀233.
我们先看k==1的情况，这比较简单，找出最长链即可。ans-=（len-1）。 之后处理k==2，显然是在k==1情况下再加一条边，也应该是最长链之类的吧，感性认识，把第一次的最长链赋为-1，跑最长链。ans-=（len-1）。 这样的话，就解决了这道题。
#include<bits/stdc++.h> #define N 100000 using namespace std; int n,k,x,y; int first[2*N+1],nex[2*N+1],to[2*N+1],val[2*N+1],siz; int p1[N+1],p2[N+1]; int mx,len; int tot; int read() { int x=0; char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x; } void add(int x,int y) { nex[siz]=first[x]; first[x]=siz; to[siz]=y; val[siz]=1; siz++; } int dfs(int x,int fa) { int mx1=0,mx2=0; for(int i=first[x];i!=-1;i=nex[i]) { int u=to[i]; if(u==fa)continue; int tmp=val[i]+dfs(u,x); if(tmp>mx1){ mx2=mx1,mx1=tmp,p2[x]=p1[x],p1[x]=i; }else if(tmp>mx2){ mx2=tmp,p2[x]=i; } } if(mx1+mx2>len)len=mx1+mx2,mx=x; return mx1; } int main() { //freopen("in.txt","r",stdin); memset(first,-1,sizeof(first)); n=read(),k=read();tot=2*(n-1); for(int i=1;i<n;i++) { x=read(),y=read(); add(x,y),add(y,x); } dfs(1,0);tot=tot-len+1; if(k==2) { len=0; for(int i=p1[mx];i;i=p1[to[i]])val[i]=val[i^1]=-1; for(int i=p2[mx];i;i=p1[to[i]])val[i]=val[i^1]=-1; dfs(1,0),tot=tot-len+1; } cout<<tot; return 0; }