首页 > 代码库 > hdu--2545--数据弱了?

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             else33                 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             else26                 cout << "pfz" << endl;27         }28     }29     return 0;30 }
View Code

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