题目链接：传送门

在线算法：

#include

#include

#include

#include

using namespace std;

const int maxn = 40010;

struct nod{

int to,next,w;

}edge[maxn*2];

int head[maxn],ip,tot;

bool vis[maxn];

int R[maxn*2],ver[maxn*2];

int dp[maxn*2][25];

int first[maxn];

int dis[maxn];

bool isroot[maxn];

void init(){

memset(head,-1,sizeof(head));

memset(isroot,0,sizeof(isroot));

memset(vis,false,sizeof(vis));

dis[1]=0,ip=0,tot=0;

}

void add(int u,int v){

edge[ip].to=v;

edge[ip].next=head[u];

head[u]=ip++;

}

/***

ver[i]=x:第i个点是x.

first[i]=x: 点i第一次出现的位置是x

R[i]=x：第i个点的深度为x;

dis[i]=x;点i到根节点的距离为x.

***/

void dfs(int u,int dept){

vis[u]=true,ver[++tot]=u,first[u]=tot,R[tot]=dept;

for(int i=head[u];i!=-1;i=edge[i].next){

int v=edge[i].to;

if(!vis[v]){

dfs(v,dept+1);

ver[++tot]=u,R[tot]=dept;

}

}

}

void ST(int n){

for(int i=1;i<=n;i++) dp[i][0]=i;

for(int i=1;(1<

for(int j=1;j+(1<

int a = dp[j][i-1],b=dp[j+(1<<(i-1))][i-1];

if(R[a]

else dp[j][i]=b;

}

}

}

int RMQ(int l,int r){

int k=0;

while(1<<(k+1)<=r-l+1)

k++;

int x = dp[l][k], y=dp[r-(1<

if(R[x]

else return y;

}

int LCA(int u,int v){

u=first[u],v=first[v];

if(u>v) swap(u,v);

return ver[RMQ(u,v)];

}

int main(){

int t,n,m;

scanf("%d",&t);

while(t--){

scanf("%d",&n);

init();

for(int i=0;i

int u,v,w;

scanf("%d%d",&u,&v);

add(u,v);

add(v,u);

isroot[v]=1;

}

int x,y;

scanf("%d%d",&x,&y);

int root;

for(int i=1;i<=n;i++){

if(!isroot[i]){

root=i;

break;

}

}

dfs(root,1);

ST(n*2-1);

printf("%d\n",LCA(x,y));

}

return 0;

}

离线算法：

#include

#include

#include

#include

using namespace std;

const int maxn = 40010;

struct nod{

int u,v,next,w,lca;

}edge[maxn*2],edge1[maxn];

int par[maxn],ancestors[maxn];

int head[maxn];

int dis[maxn],ip;

int x,y;

bool vis[maxn];

bool root[maxn];

void init(){

memset(head,-1,sizeof(head));

memset(vis,false,sizeof(vis));

for(int i=0;i

for(int i=1;i

ip=0;

}

int find_par(int x){

if(x!=par[x]) return par[x]=find_par(par[x]);

return par[x];

}

void Union(int u,int v){

u=find_par(u);

v=find_par(v);

if(u!=v) par[v]=u;

}

void add(int u,int v){

edge[ip].v=v;

edge[ip].next=head[u];

head[u]=ip++;

}

bool ans;

void tarjan(int u){

vis[u]=1;

for(int i=head[u];i!=-1;i=edge[i].next){

int v = edge[i].v;

if(!vis[v]){

dis[v]=dis[u]+edge[i].w;

tarjan(v);

Union(u,v);

}

}

if(u==x&&vis[y]&&!ans){

ans=1;

printf("%d\n",find_par(y));

return;

}

if(u==y&&vis[x]&&!ans){

ans=1;

printf("%d\n",find_par(x));

return;

}

}

int main()

{

int t,n;

scanf("%d",&t);

while(t--){

scanf("%d",&n);

init();

for(int i=0;i

int u,v;

scanf("%d%d",&u,&v);

root[v]=false;

add(u,v);

add(v,u);

}

ans=0;

scanf("%d%d",&x,&y);

for(int i=1;i<=n;i++){

if(root[i]){

tarjan(i);

break;

}

}

}

return 0;

}

 

查看原文