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大学生程序设计竞赛训练》暑期课面向全球招生!

怎么会CE???洛谷都AC了!!!

Posted by 455675787 at 2018-12-15 18:02:25 on Problem 1330
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;

ll T,n,root,d[500010],p[500010][30],from;
vector<ll> v[500010];

void dfs(ll m,ll before){
	d[m]=d[before]+1;
	p[m][0]=before;
	for(ll i=1; (1<<i)<=d[m]; i++) p[m][i]=p[p[m][i-1]][i-1];
	
	for(ll i=0; i<v[m].size(); i++){
		ll Next=v[m][i];
		if(Next!=before) dfs(Next,m);
	}
}

ll LCA(ll x,ll y){
	if(d[x]>d[y]) swap(x,y);
	for(ll i=from; i>=0; i--){
		if(d[x]<=d[y]-(1<<i)) y=p[y][i];
	}
	if(x!=y){
		for(ll i=from; i>=0; i--){
			if(p[x][i]==p[y][i]) continue;
			else{
				x=p[x][i];
				y=p[y][i];
			}
		}
		return p[x][0];
	}
	return x;
}

int main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld",&n);
		
		for(ll i=1; i<=n; i++) v[i].clear();
		memset(d,0,sizeof(d));
		memset(p,0,sizeof(p));
		root=0;
		
		from=log2(n);
		for(ll i=1; i<n; i++){
			ll x,y;
			scanf("%lld %lld",&x,&y);
			if(root==y||root==0) root=x;
			v[x].push_back(y);
			v[y].push_back(x);
		}
		dfs(root,0);
		
		ll x,y;
		scanf("%lld %lld",&x,&y);
		printf("%lld\n",LCA(x,y));	
	}
	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