[APIO2010]巡逻

树的直径

题面

给定一颗树，现可加入$k$（$k=1,2$）条边，问在加边后，从$1$号节点出发走遍所有点再回到$1$号点最小距离是多少？

解析

(前置定义：实边：本来就存在的边；虚边：新加的$k$条边之一；)

$k$的范围耐人寻味，可以尝试用分类讨论完成此题。

$k=1$

没加边时，最小距离是边数×2。
要减距离就从这些实边上来。
加了一条虚边（不是自环）后，整个图转变为一个环套树。
环越大，距离越小。
如何让环的大小最大？
把树的直径两端连起来即可。
这时最小距离改变为环的大小+环外边数×2
减少的距离为环的大小-2（因在加边之前，环其它边对距离的贡献为（环的大小-1）×2,加完后变为环的大小）。
同时等价于树的直径-1

$k=2$

这时我们要在环套树上加一条虚边。
再加一条边，会引起什么改变呢？

$step\ 1$ 虚边两端点都在环外

这肯定是更优的,减少的距离还是树的直径-1。($1$代表新加入的虚边）

$step\ 2$ 虚边一端点在环内

这样会形成两个有公共边的环。
要符合要求地走完它，就要额外把公共边多走一遍。（画图理解）
则距离减少量为-公共边数量+新纳入环的实边数-1($1$代表新加入的虚边）

$step\ 3$ 虚边两端点都在环内

这种情况貌似是上一种的特殊情况。
因为新纳入环的实边数=0
所以这种做法是不存在的。

实现

发现$step\ 1$和$step\ 2$式子可以合并，$so\ happy...$
肯定先找一遍树的直径。
然后把在环中的实边边权标为$-1$，再找一遍。
注意到这次就不能用bfs找直径了，只能用DP，反正不用找出树的直径上的边
找出的直径是不是正数，说明加边肯定亏，那就加自环吧。

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e5+100;
int n,k,h[N],cnt=1,mx,pos,dis[N],ans;
bool vis[N];
struct Edge{int to,next,w;}e[N<<1];
il void add(re int u,re int v){e[++cnt]=(Edge){v,h[u],1};h[u]=cnt;}
il int gi()
{
  re int x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
il void dpdp(re int u)
{
  vis[u]=1;
  for(re int i=h[u];i+1;i=e[i].next)
    {
      re int v=e[i].to;
      if(vis[v]) continue;
      dpdp(v);
      mx=max(mx,dis[u]+dis[v]+e[i].w);
      dis[u]=max(dis[u],dis[v]+e[i].w);
    }
}     
il void dfs(re int u,re int len)
{
  vis[u]=1;if(len>mx) mx=len,pos=u;dis[u]=len;
  for(re int i=h[u];i+1;i=e[i].next)
    {
      re int v=e[i].to;
      if(vis[v]) continue;
      dfs(v,len+e[i].w);
    }
  vis[u]=0;
}
il int dfsb(re int u)
{
  if(!dis[u]) return 1;
  for(re int i=h[u];i+1;i=e[i].next)
    {
      re int v=e[i].to;
      if(dis[v]==dis[u]-1)
    if(dfsb(v)) {e[i].w=e[i^1].w=-1;return 1;}
    }
  return 0;
}
int main()
{
  memset(h,-1,sizeof(h));
  n=gi();k=gi();ans=(n-1)*2;
  fp(i,1,n-1)
    {
      re int u=gi(),v=gi();
      add(u,v);add(v,u);
    }
  dfs(pos=1,0);//第一次找直径的第一遍DFS
  mx=-1e9;memset(dis,0,sizeof(dis));
  dfs(pos,0);//第一次找直径的第二遍DFS
  ans-=mx-1;
  if(k==1) {printf("%d\n",ans);return 0;}
  dfsb(pos);//给在直径上的边标号
  mx=0;memset(vis,0,sizeof(vis));memset(dis,0,sizeof(dis));
  dpdp(1);//第二次找直径
    ans-=mx-1;
  printf("%d\n",ans);
  return 0;
}