我也不知道 为什么这题 那么水=-=
有人在discuss说数据弱了....
求这棵树上这个结点的深度就可以了
可能是数据比较大把 为什么我的运行时间那么长呢
写了2种 一个是慢慢搜上去 一个就直接depth[]数组记录
当然也可以depth father数组混合使用 这样就可以加上 路径压缩操作了
1 #include2 #include 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 > 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 }
1 #include2 #include 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 > 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 }
好像 这套 什么 uestc的难度不大=-=