【问题描述】
你是能看到第三题的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
点点滴滴往日的眷恋，寻寻觅觅又再回到我的身边，
苦苦安顿抚平的回忆，骤然散落一如繁星的碎片……——————汪峰《回忆之前忘记之后》