Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

这个水题都能嚷昂一次

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:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator