P2016题解

262620zzj · 2024-05-24 15:06:01 · 题解

没看懂各路题解都在搞什么。直接贪心，对于一个节点，如果所有儿子都有士兵，那么在这个点放置士兵必然不如在其父亲节点放。反之，如果存在儿子没放士兵那此节点必须放。

#include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T &x){
    x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x*=f;
}
template<typename T,typename ...Args>
void read(T &x,Args &...rest){read(x);read(rest...);}
constexpr int N=1505;
struct edge{int to,nx;}e[2*N];
int head[N],tot;
inline void add_edge(int u,int v){
    e[++tot]={v,head[u]};
    head[u]=tot;
}
int ans,n;
bool exi[N];
void dfs(int u,int from){
    for(int i=head[u];i;i=e[i].nx){
        int v=e[i].to;
        if(v==from)continue;
        dfs(v,u);
        if(!exi[v])exi[u]=1;
    }
    if(exi[u])ans++;
}
int main(){
    read(n);
    for(int i=0,u,v,k;i<n;i++){
        read(u,k);
        for(int j=1;j<=k;j++){
            read(v);
            add_edge(u,v);
            add_edge(v,u);
        }
    }
    dfs(0,-1);
    printf("%d",ans);
    return 0;
}