缔造一个环出来，可以让环上的边都只访谒一次。
对付 \(k=1\)，，答案就是树的直径两边连起来。
倘若 \(k=2\)，那就先凭据 \(k=1\) 的求一遍，然后我们发明，如果第二条加的边组成的环和第一条加的边组成的环有交，那么交肯定会被访谒两次。这样交不单没有减少访谒次数，还抵消了第一次的成就。因此把第一次求出来的直径上的边权值由 \(1\) 酿成 \(-1\) 再求一遍。
#include <iostream> #include <cstdio> using namespace std; int n, k, uu, vv, hea[100005], cnt, len, zui[100005], cii[100005], zu=0; const int oo=0x3f3f3f3f; struct Edge{ int too, nxt, val; }edge[200005]; void add_edge(int fro, int too){ edge[++cnt].nxt = hea[fro]; edge[cnt].too = too; edge[cnt].val = 1; hea[fro] = cnt; } int dfs(int x, int f){ int maxi1=0, maxi2=0, qwq=0; cii[x] = zui[x] = 0; for(int i=hea[x]; i; i=edge[i].nxt){ int t=edge[i].too; if(t!=f){ int tmp=dfs(t, x)+edge[i].val; if(tmp>maxi1){ maxi2 = maxi1; maxi1 = tmp; cii[x] = zui[x]; zui[x] = i; } else if(tmp>maxi2){ maxi2 = tmp; cii[x] = i; } } } if(maxi1+maxi2>len){ len = maxi1+maxi2; zu = x; } return maxi1; } void debug(int x, int f){ if(zui[x]){ edge[zui[x]].val = -1; debug(edge[zui[x]].too, x); } if(cii[x]){ edge[cii[x]].val = -1; debug(edge[cii[x]].too, x); } } int main(){ cin>>n>>k; for(int i=1; i<n; i++){ scanf("%d%d", &uu, &vv); add_edge(uu, vv); add_edge(vv, uu); } len = 0; dfs(1, 0); int ans=2*(n-1)-(len-1); if(k==2){ for(int i=zui[zu]; i; i=zui[edge[i].too]) edge[i].val = edge[((i-1)^1)+1].val = -1; for(int i=cii[zu]; i; i=zui[edge[i].too]) edge[i].val = edge[((i-1)^1)+1].val = -1; len = 0; dfs(1, 0); ans = ans - (len - 1); } cout<<ans<<endl; return 0; }