重赋边权。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxv 100500 #define maxe 200500 #define inf 2000000000 using namespace std; int n,k,x,y,g[maxv],nume=1,fath_w[maxv],dis[maxv],pos,ret=0,root=1,tot=0,fath[maxv]; int dp1[maxv],dp2[maxv],ans=-inf; struct edge { int v,w,nxt; }e[maxe]; void addedge(int u,int v,int w) { e[++nume].v=v; e[nume].w=w; e[nume].nxt=g[u]; g[u]=nume; } void dfs1(int x) { for (int i=g[x];i;i=e[i].nxt) { int v=e[i].v; if (v!=fath[x]) { dis[v]=dis[x]+e[i].w; fath_w[v]=i;fath[v]=x; if (dis[v]>ret) { ret=dis[v]; pos=v; } dfs1(v); } } } int get_d() { dis[root]=0;ret=-inf;memset(fath,0,sizeof(fath));dfs1(root); root=pos; dis[root]=0;ret=-inf;memset(fath,0,sizeof(fath));dfs1(root); return ret; } void get_labled(int x) { while (x!=root) { e[fath_w[x]].w=e[fath_w[x]^1].w=-1; x=fath[x]; } } void dfs2(int x) { dp1[x]=dp2[x]=0; for (int i=g[x];i;i=e[i].nxt) { int v=e[i].v; if (v!=fath[x]) { dfs2(v); if (dp1[v]+e[i].w>dp1[x]) {dp2[x]=dp1[x];dp1[x]=dp1[v]+e[i].w;} else if (dp1[v]+e[i].w>dp2[x]) dp2[x]=dp1[v]+e[i].w; } } ans=max(ans,dp1[x]+dp2[x]); } int main() { scanf("%d%d",&n,&k); for (int i=1;i<=n-1;i++) { scanf("%d%d",&x,&y); addedge(x,y,1);addedge(y,x,1); } tot+=get_d(); if (k==1) {printf("%d ",2*n-1-tot);return 0;} get_labled(pos); dfs2(root);tot+=ans; printf("%d ",2*n-tot); return 0; }