P2279[HNOI2003]消防局的设立

· · 个人记录

题目传送P2279

题意

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n,tot,ans;
bool vis[1505];
int head[1505];

int dep[1505],fa[1505];
struct node{
    int to,net;
}e[3005];
struct cmp{
    bool operator () (int &a,int &b){
        return dep[a]<dep[b];
    }
};
priority_queue<int,vector<int>,cmp>q;
void add(int x,int y){
    e[++tot].to =y,e[tot].net=head[x],head[x]=tot;
    e[++tot].to =x,e[tot].net=head[y],head[y]=tot;
}
void dfs1(int x,int f,int depth){
    fa[x]=f;
    dep[x]=depth;
    for(int i=head[x];i;i=e[i].net ){
        int to=e[i].to ;
        if(to==f) continue;
        dfs1(to,x,depth+1);
    }
}
void dfs2(int x,int depth){
    if(depth>2) return ;
    vis[x]=1;
    for(int i=head[x];i;i=e[i].net ) 
      dfs2(e[i].to ,depth+1);
}
int main()
{
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        int x;
        scanf("%d",&x);
        add(i,x);
    } 
    dfs1(1,0,1);
//  for(int i=1;i<=n;i++) printf("%d %d\n",fa[i],dep[i]);
//  cout<<endl;
    for(int i=1;i<=n;i++) q.push(i);
    int x;
    while(q.size()){
        while(q.size()&&vis[x=q.top()]) q.pop();
        if(!q.size()) break;
        if(fa[fa[x]]) dfs2(fa[fa[x]],0);
        else dfs2(1,0); 
        ans++;
    }
    printf("%d",ans);
    return 0; 
 }