After many weeks of hard work, Bessie is finally getting a vacation! Being the most social cow in the herd, she wishes to visit her N (1 ≤ N ≤ 50,000) cow friends conveniently numbered 1..N. The cows have set up quite an unusual road network with exactly N-1 roads connecting pairs of cows C1 and C2 (1 ≤ C1 ≤ N; 1 ≤ C2 ≤ N; C1 ≠ C2) in such a way that there exists a unique path of roads between any two cows.
FJ wants Bessie to come back to the farm soon; thus, he has instructed Bessie that if two cows are directly connected by a road, she may not visit them both. Of course, Bessie would like her vacation to be as long as possible, so she would like to determine the maximum number of cows she can visit.
Line 1: A single integer: N Lines 2..N: Each line describes a single road with two space-separated integers: C1 and C2
Line 1: A single integer representing the maximum number of cows that Bessie can visit.
4
我是利用树状DP过的，不过Kash给我说，用topsort也可以过。。
我的代码：
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;
int dp[50005][2];
vector<int>v[50005];
bool flag[50005];
int min(int a,int b)
{
if(a>b)
return b;
else
return a;
}
void dfs(int p)
{
int i;
for(i=0;i<v[p].size();i++)
{
if(!flag[v[p][i]])
{
flag[v[p][i]]=true;
dfs(v[p][i]);
}
}
if(v[p].size()==0)
{
dp[p][0]=0;
dp[p][1]=1;
}
else
{
for(i=0;i<v[p].size();i++)
{
int j=v[p][i];
dp[p][1]=dp[p][1]+min(dp[j][1],dp[j][0]);
dp[p][0]=dp[p][0]+dp[j][1];
}
dp[p][1]++;
}
}
int main()
{
int a,b,n,i;
while(scanf("%d",&n)!=EOF)
{
memset(flag,0,sizeof(flag));
for(i=0;i<50005;i++)
v[i].clear();
memset(dp,0,sizeof(dp));
memset(flag,0,sizeof(flag));
for(i=0;i<n-1;i++)
{
scanf("%d%d",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
flag[1]=true;
dfs(1);
printf("%d/n",n-min(dp[1][0],dp[1][1]));
}
return 0;
}
