返回信息流oj257. 最近公共祖先-软件14
#include<stdio.h>
#include<string.h>
int father[100];
int fathera[100];
int fatherb[100];
int main()
{
int T,N,M,i,a,b,flag,count1,count2,flag1,flag2,q,temp,j;
scanf("%d",&T);
while(T--)
{
memset(father,0,sizeof(father));
scanf("%d",&N);
for(i=0;i<N-1;i++)
{
scanf("%d%d",&a,&b);
father[b]=a;
}
scanf("%d",&M);
for(i=0;i<M;i++)
{
scanf("%d%d",&a,&b);
if((a==1)||(b==1))
{
printf("1\n");
}
else if(a==father[b])
{
printf("%d\n",a);
}
else if(b==father[a])
{
printf("%d\n",b);
}
else
{
memset(fathera,0,sizeof(fathera));
memset(fatherb,0,sizeof(fatherb));
count1=count2=0;
flag1=flag2=0;
temp=a;
while(temp!=1)
{
temp=father[temp];
if(temp==b)
{
flag1=1;
}
fathera[count1++]=temp;
}
temp=b;
while(temp!=1)
{
temp=father[temp];
if(temp==a)
{
flag2=1;
}
fatherb[count2++]=temp;
}
if(flag1)
{
printf("%d\n",b);
}
else if(flag2)
{
printf("%d\n",a);
}
else
{
flag=0;
for(j=0;j<count1;j++)
{
for(q=0;q<count2;q++)
{
if(fathera[j]==fatherb[q])
{
printf("%d\n",fathera[j]);
flag=1;
break;
}
}
if(flag)
break;
}
}
}
}
}
return 0;
}
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #92396同步于 2017/3/15
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】求改正，自己电脑上是对的，oj上错了257. 最近公共祖先
gungnir0123
2017/3/15镜像同步10 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
【 在 gungnir0123 的大作中提到: 】
: 求帮忙看看，改了一晚上都没找到错哪了
内存改大一点，然后加入a==b时的判定，你的源代码如果a==b且a！=1时会输出1。
【 在 SHawnHardy 的大作中提到: 】
:
: 内存改大一点，然后加入a==b时的判定，你的源代码如果a==b且a！=1时会输出1。[upload=1][/upload][upload=2][/upload]
谢谢，刚改了下，确实是忘记考虑a==b的情况了，太感谢了
【 在 SHawnHardy 的大作中提到: 】
:
: 内存改大一点，然后加入a==b时的判定，你的源代码如果a==b且a！=1时会输出1。[upload=1][/upload][upload=2][/upload]
试了自己之前设的内存，大小是够用的
【 在 gungnir0123 的大作中提到: 】
: 试了自己之前设的内存，大小是够用的
不不不，你看题目要求，节点个数是可以为100的，所以碰到极限数据你开长度为100的数组会段错误的
【 在 SHawnHardy 的大作中提到: 】
: 不不不，你看题目要求，节点个数是可以为100的，所以碰到极限数据你开长度为100的数组会段错误的
节点个数最大为100，我数组开到100应该刚好吧，我提交到oJ也是正确的
【 在 SHawnHardy 的大作中提到: 】
:
: 内存改大一点，然后加入a==b时的判定，你的源代码如果a==b且a！=1时会输出1。[upload=1][/upload][upload=2][/upload]
求大神帮忙看看我这个代码，也是这个题目，java写的也是找不到错误在哪。OJ给的是答案错误的提示。
我的思路是，TreeNode只记录父亲就OK。然后tree是一个TreeNode[N+1]的数组，tree[0]是一个虚节点，不使用。tree[i]就是第i个节点。 然后用两个ArrayList分别记录从u、v走到root的进过的所有节点，也就是一条路径。 然后两个ArrayList一起从尾部开始比较（从root开始比较），直到不相等或者某个路径走完，上一个相等的节点就是 最近公共祖先。
```JAVA
import java.util.*;
class TreeNode
{
public int parent;
public TreeNode(int parent1)
{
this.parent = parent1;
}
}
public class Main{
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for (int i = 0; i < T; i++) {
int N = in.nextInt();
//开始构建树
TreeNode[] tree = new TreeNode[N + 1];
for (int j = 1; j < N; j++) {
int pa = in.nextInt();
int ch = in.nextInt();
tree[ch] = new TreeNode(pa);
if (tree[pa] == null)
{
tree[pa] = new TreeNode(0);
}
}
int M = in.nextInt();
//开始查询
for (int j = 0; j < M; j++) {
int v = in.nextInt();
int u = in.nextInt();
//获得vu到root的路径
List<Integer> pathV = new ArrayList<Integer>();
List<Integer> pathU = new ArrayList<Integer>();
int cur = v;
while(cur != 0)
{
pathV.add(cur);
cur = tree[cur].parent;
}
cur = u;
while(cur != 0)
{
pathU.add(cur);
cur = tree[cur].parent;
}
//从root分别到vu，寻找最近公共祖先
int ancestor = 0;
int indexV = pathV.size() - 1;
int indexU = pathU.size() - 1;
while (indexV >= 0 && indexU >= 0) {
if (pathV.get(indexV) != pathU.get(indexU)) {
break;
}
ancestor = pathV.get(indexV);
indexV--;
indexU--;
}
System.out.println(ancestor);
}
}
in.close();
}
}
```
【 在 gungnir0123 的大作中提到: 】
:
: 节点个数最大为100，我数组开到100应该刚好吧，我提交到oJ也是正确的
也是醉了。。。数组开到100，是不能访问下标为100的值的。研究生机试应该考完了吧，java我不太熟，我就不给你看了