항 저 우 전기 2545 나무 전쟁 (그리고 수집)

나무 위의 전쟁
Time Limit: 10000/4000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 782    Accepted Submission(s): 425
Problem Description
나무 한 그루 에 게 나무 위의 한 노드 가 누 군가 차지 하면 그의 모든 아들 이 차지 합 니 다. lxh 와 pfz 는 처음에 각각 두 노드 에 서 있 었 습 니 다. 누가 현재 있 는 점 을 다른 사람 이 차지 하면 그 는 시합 에서 졌 습 니 다. 누가 이 길 수 있 느 냐 고 물 었 습 니 다.
 
Input
다 중 그룹 데이터 입력
각 조 의 첫 줄 에는 두 개의 수 N, M (N, M < = 100000), N 은 나무의 노드 수 를 나타 내 고 M 은 문의 수 를 나타 내 며 N = M = 0 은 입력 이 끝 났 음 을 나타 낸다.노드 의 번 호 는 1 에서 N 이다.
다음 N - 1 줄, 줄 당 2 개의 정수 A, B (1 < = A, B < = N) 는 번호 가 A 인 노드 가 번호 가 B 인 노드 의 아버지 임 을 나타 낸다.
다음 M 줄 은 줄 마다 2 개의 숫자 가 있 습 니 다. lxh 와 pfz 의 초기 위 치 를 나타 내 는 번호 X, Y (1 < = X, Y < = N, X! = Y), lxh 는 항상 먼저 이동 합 니 다.
 
Output
질문 할 때마다 한 줄 을 출력 하고 우승자 의 이름 을 출력 합 니 다.
 
Sample Input

   
   
   
   

    
    
    
     2 1
 1 2
 1 2
 5 2
 1 2
 1 3
 3 4
 3 5
 4 2
 4 5
 0 0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
     lxh
 pfz
 lxh

   
   
   
   
   
   
   
   


   
   
   
   

먼저 문제 의 대 의 를 분석 해 보 자. lxh 가 먼저 움 직 이 고 누가 먼저 뿌리 노드 를 차지 하 며 누가 이 기 는 지. 여기 서 우 리 는 경로 가 압축 되 지 않 는 다 는 것 을 기억 하고 경로 가 압축 되면 결과 에 영향 을 줄 수 있다.(여러분 을 오도 하지 않 기 위해 저 는 특별히 WA 를 제출 했 습 니 다.) 그러나 사례 중의 데이터 가 비교적 적 고 경로 압축 이 작용 하지 않 았 기 때문에 사례 는 지 나 쳤 습 니 다.
여기 서 경로 압축 의 역할 은 여러분 도 알 고 있 을 것 입 니 다. 그래서 템 플 릿 에 의존 하여 문 제 를 푸 는 어린이 들 에 게 경로 압축 부분 을 없 애 는 것 을 잊 지 말 라 고 일 깨 워 드 립 니 다.
여기 서 문제 풀이 의 주요 부분 을 상세 하 게 설명 한다.
만약 뿌리 노드 를 찾는다 면, 우 리 는 find 작업 을 할 수 있 습 니 다. 왜냐하면 잎 에서 뿌리 노드 를 찾 는 것 은 한 걸음 한 걸음 씩 돌아 가 는 것 이기 때 문 입 니 다.그래서 우 리 는 여기에서 한 걸음 한 걸음 위로 찾 을 때마다 + 1 번 조작 해 야 한다.
4. 567913. 그리고 완전한 AC 코드 입 니 다.

int find(int a)
{
    int r=a;
    int cishu=0;//           
    while(f[r]!=r)
    {
        cishu++;
        r=f[r];
    }
    return cishu;
}