懒得再写一遍。
三个状态,表示包含root点,不包含root点,不包含root点和任意一条链的子树最优值。
#define INF 9999999
int N;
vector < int > t[101];
int f[101][3];
int used[101];
int min ( int a, int b )
{
return a < b ? a : b;
}
void dfs ( int u )
{
used[u] = 1;
vector < int > child;
int i, j;
for ( i = 0; i < t[u].size (); i ++ )
{
if ( !used[t[u][i]] )
{
dfs ( t[u][i] );
child.push_back ( t[u][i] );
}
}
if ( child.size () == 0 )
{
f[u][0] = INF, f[u][1] = 0, f[u][2] = INF;
return;
}
int sum = 0;
for ( i = 0; i < child.size (); i ++ )
sum += f[child[i]][0];
f[u][1] = min ( f[u][1], sum );
for ( i = 0; i < child.size (); i ++ )
{
int ci = child[i], temp = sum - f[ci][0];
temp += min ( f[ci][1], f[ci][2] );
f[u][2] = min ( f[u][2], temp );
}
for ( i = 0; i < child.size (); i ++ )
{
int ci = child[i], temp = sum - f[ci][0];
temp += f[ci][2] + 1;
f[u][0] = min ( temp, f[u][0] );
}
for ( i = 0; i < child.size (); i ++ )
{
for ( j = i + 1; j < child.size (); j ++ )
{
int ci = child[i], cj = child[j];
int temp = sum - f[ci][0] - f[cj][0];
temp += min ( f[ci][1], f[ci][2] ) + min ( f[cj][1], f[cj][2] ) + 1;
f[u][0] = min ( temp, f[u][0] );
}
}
}
int main ()
{
//freopen ( "in.txt", "r", stdin );
while ( cin >> N )
{
int i;
for ( i = 1; i <= N; i ++ )
t[i].clear ();
for ( i = 1; i < N; i ++ )
{
int u, v;
cin >> u >> v;
t[u].push_back ( v );
t[v].push_back ( u );
}
for ( i = 1; i <= N; i ++ )
f[i][0] = f[i][1] = f[i][2] = INF;
memset ( used, 0, sizeof ( used ) );
dfs ( 1 );
if ( f[1][0] == INF )
printf ( "-1/n" );
else
printf ( "%d/n", f[1][0] );
}
return 0;
}