OJ题号：BZOJ1217、洛谷2279

思路：贪心。

先O(n)递推记录各个结点的深度，然后从深度大的结点贪心，如果当前结点不安全，就在它爷爷地方开消防局，同时更新上下二代的安全信息。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 const int N=1001; 7 int p[N]; 8 bool safe[N]= {
   0}; 9 std::vector
          
            c[N];10 struct Vertex {11 int id,depth;12 bool operator > (const Vertex &x) const {13 return this->depth>x.depth;14 }15 };16 Vertex v[N];17 void update(const int x) {18 safe[p[x]]=safe[p[p[x]]]=true;19 for(unsigned int i=0; i
           
            ());40 int ans=0;41 for(int i=1; i<=n; i++) {42 if(safe[v[i].id]) continue;43 update(p[p[v[i].id]]);44 ans++;45 }46 printf("%d\n",ans);47 return 0;48 }