又是外面的 OJ ...
火车头带着交了，Time Limit Exceeded.
哦，原来有多测。
while(scanf("%d", &n) != EOF)
再交
Accepted.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100005
int f[N][2], first[N], Next[N], to[N], h[N], vis[N], fa[N], tot, n;
void add(int x, int y)
{
Next[++tot] = first[x];
first[x] = tot;
to[tot] = y;
return;
}
void dp(int u)
{
if(vis[u])
{
return;
}
vis[u] = 1;
for(int i = first[u]; i; i = Next[i])
{
int v = to[i];
if(vis[v])
{
continue;
}
dp(v);
f[u][0] += f[v][1];
f[u][1] += min(f[v][0], f[v][1]);
}
return;
}
int main()
{
ios::sync_with_stdio(false);
while(scanf("%d", &n) != EOF)
{
tot = 0;
memset(first, 0, sizeof(first));
memset(vis, 0, sizeof(vis));
memset(fa, 0, sizeof(fa));
for(int i = 0; i <= n; i++)
{
f[i][0] = 0;
f[i][1] = 1;
}
int u, cnt, v;
for(int i = 1; i <= n; i++)
{
scanf("%d:(%d)", &u, &cnt);
for(int j = 1; j <= cnt; j++)
{
scanf("%d", &v);
add(u, v);
add(v, u);
fa[v] = u;
}
}
int root;
for(int i = 1; i <= n; i++)
{
if(!fa[i])
{
root = i;
break;
}
}
dp(root);
printf("%d\n", min(f[root][0], f[root][1]));
}
return 0;
}