o[f[w]] = 1;
请问为什么要去掉标记父亲这一行才能过,和P3942的贪心有什么不同吗。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define N 1505
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,t,b[N],f[N],d[N],o[N],ans,v;
vector<int>e[N];
bool cmp(int x,int y){return d[x]>d[y];}
void dfs(int u,int fa){
f[u] = fa;
d[u] = d[fa]+1;
for(int v:e[u]){
if(v==fa) continue;
dfs(v,u);
}
}
int main(){
scanf("%d",&n);b[1]=1,o[1]=o[0]=N;
for(int i=1;i<=n;i++){
int id,x;scanf("%d%d",&id,&x);id++;
while(x--){
int y;scanf("%d",&y);y++;
e[id].emplace_back(y);
e[y].emplace_back(id);
}
b[i] = i;
o[i] = N;
}
dfs(1,0);
sort(b+1,b+n+1,cmp);
o[0]=0; //加上这一句
FOR(i,1,n){
v=b[i];
int w = f[v];
o[v]=min(o[v],o[w]+1);
if(o[v]>1){
o[w]=0,ans++;
//o[f[w]] = 1;
}
}printf("%d",ans);
}