讨论 / 树剖可秒。
Assassin1 2019-03-09 21:23:05
点我顶贴 收藏 删除
#include<iostream>

#include<stdio.h>

#include<string.h>

using namespace std;

const int N=5e5+7;

struct data {

int to,next;

} e[N<<1];

int head[N],size[N],son[N],bl[N],S,cnt,n,m,i,j,fa[N],d[N];

int Pow(int a,int b) {

int ans = 1;

int base = a;

while(b) {

if(b & 1) ans *= base;

base *= base;

b >>= 1;

}

return ans;

}

int pow_mod(int a,int b,int c) {

int ans = 1;

int base = a%c;

while(b) {

if(b & 1) ans = (ans*base)%c;

base = (base*base)%c;

b >>= 1;

}

return ans;

}

void ins(int u,int v) {

e[++cnt].to=v;

e[cnt].next=head[u];

head[u]=cnt;

}

void insert(int u,int v) {

ins(u,v);

ins(v,u);

}

void dfs1(int x) {

size[x]=1;

son[x]=0;

for(int i=head[x]; i; i=e[i].next)if(e[i].to!=fa[x]) {

fa[e[i].to]=x;

d[e[i].to]=d[x]+1;

dfs1(e[i].to);

size[x]+=size[e[i].to];

if(size[e[i].to]>size[son[x]])son[x]=e[i].to;

}

}

void dfs2(int x,int chain) {

bl[x]=chain;

if(son[x])dfs2(son[x],chain);

for(int i=head[x]; i; i=e[i].next)

if(e[i].to!=son[x]&&e[i].to!=fa[x])dfs2(e[i].to,e[i].to);

}

int lca(int x,int y) {

for(; bl[x]!=bl[y]; d[bl[x]]>d[bl[y]]?x=fa[bl[x]]:y=fa[bl[y]]);

return d[x]<d[y]?x:y;

}

int main() {

memset(head,0,sizeof(head));

memset(size,0,sizeof(size));

memset(son,0,sizeof(son));

memset(bl,0,sizeof(bl));

memset(fa,0,sizeof(fa));

memset(d,0,sizeof(d));

memset(e,0,sizeof(e));

m=1;

int p=0;

// S=1;

for(scanf("%d",&n),i=1; --n; ++i,p++) {

scanf("%d%d",&i,&j),insert(i,j);

if(p==0) {

S=i;

}

}

for(dfs1(S),dfs2(S,S); m--;)scanf("%d%d",&i,&j),printf("%d\n",lca(i,j));

}

查看更多回复
提交回复