hdu--2545--数据弱了？

我也不知道为什么这题那么水=-=

有人在discuss说数据弱了....

求这棵树上这个结点的深度就可以了

可能是数据比较大把为什么我的运行时间那么长呢

　　touch me

写了2种一个是慢慢搜上去一个就直接depth[]数组记录

当然也可以depth father数组混合使用这样就可以加上路径压缩操作了

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 const int size = 100010;
 6 int father[size];
 7 
 8 int find( int x , int ans )
 9 {
10     return father[x] == -1 ? ans : find( father[x] , ans+1 );
11 }
12 
13 int main()
14 {
15     cin.sync_with_stdio(false);
16     int n , m , x , y , xx , yy;
17     while( cin >> n >> m && (n||m) )
18     {
19         memset( father , -1 , sizeof(father) );
20         for( int i = 0 ; i<n-1 ; i++ )
21         {
22             cin >> x >> y;
23             father[y] = x;
24         }
25         while( m-- )
26         {
27             cin >> x >> y;
28             xx = find(x,0);
29             yy = find(y,0);
30             if( xx<=yy )
31                 cout << "lxh" << endl;
32             else
33                 cout << "pfz" << endl; 
34         }
35     }
36     return 0;
37 }

View Code

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 const int size = 100010;
 6 int depth[size];
 7 
 8 int main()
 9 {
10     cin.sync_with_stdio(false);
11     int n , m , x , y;
12     while( cin >> n >> m &&(n||m) )
13     {
14         memset( depth , 0 , sizeof(depth) );
15         for( int i = 0 ; i<n-1 ; i++ )
16         {
17             cin >> x >> y;
18             depth[y] = depth[x] + 1;
19         }
20         while(m--)
21         {
22             cin >> x >> y;
23             if( depth[x]<=depth[y] )
24                 cout << "lxh" << endl;
25             else
26                 cout << "pfz" << endl;
27         }
28     }
29     return 0;
30 }

View Code

好像这套什么 uestc的难度不大=-=

just follow your heart