OJ题号：BZOJ1217、洛谷2279
思路：贪心。
先O(n)递推记录各个结点的深度，然后从深度大的结点贪心，如果当前结点不安全，就在它爷爷地方开消防局，同时更新上下二代的安全信息。
1 #include<cstdio> 2 #include<vector> 3 #include<cstring> 4 #include<algorithm> 5 #include<functional> 6 const int N=1001; 7 int p[N]; 8 bool safe[N]= {0}; 9 std::vector<int> 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<c[p[x]].size(); i++) safe[c[p[x]][i]]=true; 20 for(unsigned int i=0; i<c[x].size(); i++) { 21 safe[c[x][i]]=true; 22 for(unsigned int j=0; j<c[c[x][i]].size(); j++) { 23 safe[c[c[x][i]][j]]=true; 24 } 25 } 26 } 27 int main() { 28 int n; 29 scanf("%d",&n); 30 p[1]=1; 31 v[1].id=1; 32 v[1].depth=0; 33 for(int i=2; i<=n; i++) { 34 v[i].id=i; 35 scanf("%d",&p[i]); 36 c[p[i]].push_back(i); 37 v[i].depth=v[p[i]].depth+1; 38 } 39 std::sort(&v[1],&v[n+1],std::greater<Vertex>()); 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 ",ans); 47 return 0; 48 }