Debug

Description

经过了一整夜的激战，rc的部队终于攻下了虫族的首都Bugzilla。现在，rc决定亲自带领一队突击队员在虫族庞大的地道中寻找他的宿命之敌—Bug。
　　Bugzilla由N个基地组成。这N个基地被N-1段双向地道连接在一起，每段地道都连接两个基地，并且保证任意两个基地之间都可以通过地道互相到达。Bug就藏在其中的某段地道中。
　　开始时rc可以乘坐运输机降落在任何一个基地。每次到达一个基地时，rc都可以选择呼叫运输机将他和他的部队运输到任意另一个基地，或者进入与这个基地相邻的一段地道进行搜索。但为了防止Bug跑进已经搜索过的地道，他在离开一个基地进入地道或登上运输机时一定会将这个基地炸毁。基地一旦被炸毁就不再和与它相邻的地道连接。但这样一来，如果进入的地道另一端的基地已经在之前被炸毁，rc和他的部下就将被永远困在地道中。因为地道生活并不有趣，所以在这种情况下rc是不会进入这段地道的。
　　不过，这也带来了一个问题，就是rc也许不能搜索所有的地道了。现在rc想知道的是他最多能搜索多少段地道。作为有幸被留在运输机上看风景而不必冒着成为虫食的危险钻入地下的人，你必须完成这个任务!

Input

第一行一个整数N(2<=N<=100000)，表示基地的个数。基地被编号为1~N的整数。
以下N-1行，每行两个整数A和B，表示编号为A的基地和编号为B的基地间有一段地道。

Output

一个整数，表示RC最多能搜索的地道的数目

Sample Input

6
1 2
3 2
2 4
4 5
4 6

Sample Output

4

Hint

数据范围：
对于20%的数据，2 <= N <= 30
对于50%的数据，2 <= N <= 10000

解题思路

题目意思：让你删除最少边，使得所有点的度小于等于2

因为当这个点有大于1个叶子节点时，往下绝对会比往上更优，因为如果和父亲节点连边，必须要放弃它的所有儿子节点，而在儿子节点大于1个时，删除与父亲的边不可能比删除儿子的边更优。

所以在度数大于二时，优先删除和父节点连的边

在DFS的时候只要有点的度数大于2，就删除它的父亲节点的边，如果还是大于2，就任选几条儿子删了，最后留下2条儿子

AC代码

#include<cstdio>
#include<iostream>
using namespace std;
int n,s,tot,b[1000005],du[1000005],head[1000005];
struct node
{
   
	int to,next;
}a[1000005];
void add(int x, int y)//邻接表
{
   
	a[++tot]=(node){
   y,head[x]};
	head[x]=tot;
}
void dp(int x,int father)//dp
{
   
	b[x]=1;//标记
	if(du[x]==1&&a[head[x]].to==father)return;//剪枝
	for(int i=head[x];i;i=a[i].next)
	{
   
		int y=a[i].to;
		if(b[y]==1)continue;
		dp(y, x);//递归
	}
	if(du[x]>2)//如果度大于2
	{
   
		s=s-(du[x]-2);//累加
		du[father]--;//删边
	}
}
int main()
{
   
	scanf("%d",&n);
	s=n-1;//初值
	for(int i=1;i<=n-1;i++)
	{
   
		int x, y;
		scanf("%d%d",&x,&y);
		du[x]++;//度++
		du[y]++;
		add(x,y);//邻接表
		add(y,x);
	}
	dp(1,0);//dp
	printf("%d",s);//输出
}

谢谢