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

## 怎么会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: