Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 这个水题都能嚷昂一次

Posted by KatrineYang at 2016-09-08 09:31:21 on Problem 1330
```#include <iostream>
#include <stdio.h>
using namespace std;

int root;
int parent[10005];

int depth[10005];

void getDepth(int node){
if(depth[node] != -1) return;
getDepth(parent[node]);
depth[node] = depth[parent[node]] + 1;
}

int main() {
int T;
scanf("%d", &T);
for(int ii = 0; ii < T; ii++){
int N;

int sucCnt[10005] = {0};

scanf("%d", &N);
for(int i = 0; i < N-1; i++){
int par, suc;
scanf("%d%d", &par, &suc);
parent[suc] = par;
sucCnt[suc]++;
}
for(int i = 1; i <= N; i++){
if(sucCnt[i] == 0){
root = i;
break;
}
}
for(int i = 1; i <= N; i++) depth[i] = -1;
depth[root] = 0;
for(int i = 1; i <= N; i++) getDepth(i);
int a, b;
scanf("%d%d", &a, &b);
if(depth[a] > depth[b]){
int cha = depth[a]-depth[b];
for(int i = 0; i < cha; i++) a = parent[a];
}
else{
int cha = depth[b]-depth[a];
for(int i = 0; i < cha; i++) b = parent[b];
}
while(a!=b){
a = parent[a];
b = parent[b];
}
printf("%d\n", a);
}
return 0;
}
```

Followed by: