1 second

256 megabytes

standard input

standard output

You are given a rooted tree with vertices numerated from 11 to nn. A tree is a connected graph without cycles. A rooted tree has a special vertex named root.

Ancestors of the vertex ii are all vertices on the path from the root to the vertex ii, except the vertex ii itself. The parent of the vertex ii is the nearest to the vertex ii ancestor of ii. Each vertex is a child of its parent. In the given tree the parent of the vertex ii is the vertex pipi. For the root, the value pipi is −1−1.

An example of a tree with n=8n=8, the root is vertex 55. The parent of the vertex 22 is vertex 33, the parent of the vertex 11 is vertex 55. The ancestors of the vertex 66 are vertices 44 and 55, the ancestors of the vertex 77 are vertices 88, 33 and 55

You noticed that some vertices do not respect others. In particular, if ci=1ci=1, then the vertex ii does not respect any of its ancestors, and if ci=0ci=0, it respects all of them.

You decided to delete vertices from the tree one by one. On each step you select such a non-root vertex that it does not respect its parent and none of its children respects it. If there are several such vertices, you select the one with the smallest number. When you delete this vertex vv, all children of vv become connected with the parent of vv.

5

3 1

1 1

-1 0

2 1

3 0

1 2 4

5

-1 0

1 1

1 1

2 0

3 0

-1

8

2 1

-1 0

1 0

1 1

1 1

4 0

5 1

7 0

5

n the second example you don't need to delete any vertex:

• vertices 22 and 33 have children that respect them;
• vertices 44 and 55 respect ancestors.
• 

In the third example the tree will change this way:

解题思路：

 #include<iostream>

 #include<vector>

 #include<string.h>

 using namespace std;

 int n ;

 int tp1 , tp2;

 vector<int>a[];

 int b[];

 int c[];

 int main()

 {

     cin>>n;

     memset(b,,sizeof(b));

     memset(c,,sizeof(c));

     for(int i =  ; i <= n; i++)

     {

         cin>>tp1>>tp2;

         if(tp1!=-)      //如果它不是根结点；

         {

             a[tp1].push_back(i);  //则放入它的父亲；

         }

         b[i] = tp2;    //并记录tp2，看它自己本身是否尊重父亲；

     }

     int flag;

     for(int i =  ; i <=n ;i++)

     {

         flag = ;

         for(int j =  ;j < a[i].size() ;j++)

         {

             if(b[a[i][j]]==)

             {

                 flag = ;

                 break;

             }

         }

         c[i] = flag ;    //这个是用来记录它的孩子是否尊重父亲；

     }

     int flaggg = ;

     for(int i =  ; i <= n ;i++)

     {

         if(c[i]==&&b[i]==)    //如果它的孩子不尊重父亲并且它自己也不尊重父亲；

         {

             cout<<i<<" ";

             flaggg = ;

         }

     }

     if(flaggg==)

     {

         cout<<-;

     }

     return ;

 }