链接：P3629 [APIO2010] 巡逻。

题意

有一棵节点数为 $n$ 的树，要求我们在树上加上 $k$ 条边，使以根（ $1$ 号节点）为起点遍历时经过的”路径”最短。关于“路径”，有以下几个要求：

加的边必须且仅经过 $1$ 次。
允许出现自环。
从 $1$ 号节点出发，回到 $1$ 号节点。

要求输出这个路径最小值。

数据范围

$3 ≤ n ≤ 100,000$ , $1 ≤ K ≤ 2$ 。

点击查看题解

题解

分类讨论。以下的”贡献“指对所减少的路径长度的贡献， $f(k)$ 指取相应的 $k$ 时满足的最短路径长度。

由于连边所形成的环上的边都会贡献 $1$ ，所以可以设边权为 $1$ 。

`k=1`

~~显而易见地~~，我们要在整棵树的任一直径端点两点连边，这样贡献是最大的。

计算贡献：环上的边集中的边都少走了一次，都贡献 $1$ ；新连的边贡献 $-1$ 。设环贡献为 $E_1$ ，则 $f(1)=f(0)-E_1+1$ 。

`k=2`

何连边

我们要在 k=1 的基础（直径端点连一条边）上再讨论连边，这样会存在最大贡献。证明：

如图， $1$ 和 $12$ 或 $13$ 间的距离为直径。假设我们不连直径两端，而是连接了一些”枝桠“，那么它们其中一个所形成的环完全可以用直径所形成的环替换，贡献不会更差。

实际上，我们证明的是：所连边中一定有直径两端点。

需要用 dfs 来求直径，由于后面需要标记一条直径上的点。

算贡献

如果连的第二条边所形成的环没有与第一条边所形成的环重合，自然互不影响，则分别计算贡献。

如果有贡献，需要知道两环的重合部分。~~显而易见地~~，重合部分需走两次；换言之，重合的边贡献为 $-1$ 。故，在计算 k=2 时可以在 k=1 时的环上的边权设为 $-1$ 。

连何边

再连一个直径即可。由于边权有负数，需选择树形 DP 求解。（一道题中竟然需要使用 $2$ 种求直径的方法）

原理上： $f(2)=f(1)-E_2+(E_1\cap E_2)+1$ 。

若 $E_2$ 指求的直径贡献，则 $f(2)=f(1)-E_2+1$ 。

代码

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	const int N=100000+5,Flag=-114;
	struct edge{int nxt,to;}e[N*4];
    int n,k,cnt=0,head[N],dis[N],pre[N],w=0;
	int tag[N],fir[N],sec[N];
    void add(int a,int b)
    {
    	e[++cnt]=(edge){head[a],b};
    	head[a]=cnt;
	}
	void dfs_1(int root,int dad)
	{
		for(int i=head[root];i;i=e[i].nxt)
		{
			int son=e[i].to;
			if(son==dad) continue;
			dis[son]=dis[root]+1;
			pre[son]=root;
			dfs_1(son,root);
		}
	}
	int dfs_2(int root,int dad)
	{
		int maxl=Flag,ret=Flag;
		for(int i=head[root];i;i=e[i].nxt)
		{
			int son=e[i].to;
			if(son==dad) continue;
			ret=max(dfs_2(son,root),ret);
			if(tag[root]&&tag[son]) maxl=fir[son]-1;
			else maxl=fir[son]+1;
			if(maxl>fir[root]) sec[root]=fir[root],fir[root]=maxl;
			else if(maxl>sec[root]) sec[root]=maxl;
			ret=max(ret,fir[root]+sec[root]);	
		}
		return ret;
	}
    void yzmain()
    {
    	int t1,t2,p1,p2,p3;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n-1;i++)
        	scanf("%d%d",&t1,&t2),
        	add(t1,t2),add(t2,t1),w+=2;
        memset(dis,0,sizeof(dis));t1=Flag;p1=1;pre[p1]=Flag;
		dfs_1(p1,p1);
        for(int i=1;i<=n;i++)
        	if(t1<dis[i]) t1=dis[i],p2=i;
        memset(dis,0,sizeof(dis));t1=Flag;pre[p2]=Flag;
		dfs_1(p2,p2);
        for(int i=1;i<=n;i++)
        	if(t1<dis[i]) t1=dis[i],p3=i;
        if(k==1) {printf("%d\n",w-t1+1);return;}
        do{
        	tag[p3]=1;p3=pre[p3];
		}while(p3!=Flag);
		printf("%d\n",w-t1+1-dfs_2(p2,p2)+1);
        return;
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    _yz::yzmain();
    return 0;
}