【问题描述】
你是能看到第三题的friends呢。
——aoao
树是个好东西,删掉树一条边要1的代价,随便再加一条边有1的代价,求最小的代价把树变成环。
【输入格式】
第一行一个整数,代表树的点数。
接下来−1行,每行两个数代表树的一条边。
【输出格式】
一行一个整数代表答案。
【样例输入】
4
1 2
2 3
2 4
【样例输出】
3
【数据规模与约定】
对于30%的数据,1≤n≤10。
对于60%的数据,1≤n≤1000。
对于100%的数据,1≤n≤100000。

题解:
         ①这是贪心还是DP还是构造还是Implentation……(我们争论了一会儿~)

         ②个人比较支持构造,最优的策略是:

               思路:尝试先将树弄成一条链,最后加一条边变成环。

               分类讨论: 

                   (1)当前点仅有一个子节点,那么什么都不做。

                   (2)当前点有1个以上的依旧相连子节点,那么此时最优的方案就是选取两个儿子

                      组成一条链,其余的儿子的边直接断掉,并且将这个点和父亲的连边断掉。

              上述过程使用递归完成,并记录断边个数x。

              由于最后整个树被拆成了x+1条链(或者点),然后在顺次连x+1条边就形成环。

              因此最终答案就是x+x+1。

#include<cstdio>
#include<iostream>
#define N 100001
using namespace std;
int front[N],nxt[N<<1],to[N<<1],tot;
int ans;
void add(int u,int v)
{
    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;
    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;
}
int dfs(int x,int f)
{
    int sum=0;
    for(int i=front[x];i;i=nxt[i])if(to[i]!=f) sum+=dfs(to[i],x);
    if(sum>=2)
    {
        if(x==1) ans+=sum-2;
        else ans+=sum-1;
        return 0;
    }
    return 1;
}
int main()
{
    int n,u,v;scanf("%d",&n);
    for(int i=1;i<n;i++)scanf("%d%d",&u,&v),add(u,v);
    dfs(1,0);printf("%d",ans*2+1);
}//Ztraveler

点点滴滴往日的眷恋,寻寻觅觅又再回到我的身边,

苦苦安顿抚平的回忆,骤然散落一如繁星的碎片……——————汪峰《回忆之前忘记之后》