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

## 题好水，人更水……

Posted by Ruby931031 at 2012-07-09 00:43:11 on Problem 1330
```//真是杀鸡用牛刀。。
//链式前向星,并查集,Tarjan_Offline_LCA
//以后试着写写RMQ的
//32ms
#include <stdio.h>
#include <string.h>
#define MAXN 10010
struct Edge{
int to;
int next;
};

Edge edge[MAXN+10];
bool bFind,isroot[MAXN+10],visit[MAXN+10];

int find(int x){
if (p[x]!=x)	p[x] = find(p[x]);
return p[x];
}

void LCA(int u){
p[u] = u;
visit[u]=true;

if (!visit[edge[k].to])
{
LCA(edge[k].to);
p[edge[k].to]=u;
if (bFind)	return;
}

if (u==qx && visit[qy])
{
printf("%d\n",find(qy));
bFind = true;
return;
}
if (u==qy && visit[qx])
{
printf("%d\n",find(qx));
bFind = true;
return;
}
}

int main()
{
int t,n,i,s,e,rear;
scanf("%d",&t);
while (t--)
{
rear=0;
scanf("%d",&n);
memset(isroot,true,sizeof(isroot));
memset(visit,0,sizeof(visit));

for (i=1;i<n;i++)
{
scanf("%d %d",&s,&e);	//链式前向星
isroot[e] = false;
edge[rear].to = e;
}
scanf("%d %d",&qx,&qy);

for (i=1;i<=n;i++)		//找到根节点
if (isroot[i])	break;
bFind = false;
LCA(i);
}
return 0;
}```

Followed by: