求大神指导啊感激不尽：
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstring>
#include<iterator>
using namespace std;

const int maxn=10002;
int T,n,root,num,p,q;
int rmq[maxn][18],father[maxn],first[30006],h[2*maxn],dfs[2*maxn];
vector<int> children[maxn];

int min(int x,int y)
{
	return x<y? x:y;
}

void DFS(int x,int depth)
{
	num++;
	dfs[num]=x;
	h[num]=depth;
	rmq[num][0]=num;
	if (!first[x])
		first[x]=num;
	for (vector<int>::iterator iter=children[x].begin();iter<children[x].end();iter++)
	{
		DFS(*iter,depth+1);
		if (iter==children[x].end()-1)
			break;
		num++;
		dfs[num]=x;
		h[num]=depth;
		rmq[num][0]=num;
	}
}

void RMQ()
{
	for (int j=1;j<17;j++)
	{
		int rl,s;
		s=1<<(j-1);
		for (int i=0;i+s-1<=num;i++)
		{
			rl=i+s;
			rmq[i][j]=h[rmq[i][j-1]]<h[rmq[rl][j-1]]? rmq[i][j-1]:rmq[rl][j-1];
		}
	}
}

void init()
{
	int fa,ch;
	num=-1;
	memset(father,0,sizeof(father));
	memset(first,0,sizeof(first));
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		children[i].clear();
	for (int i=1;i<n;i++)
	{
		scanf("%d%d",&fa,&ch);
		father[ch]=fa;
		children[fa].push_back(ch);
	}
	for (int i=1;i<=n;i++)
		if (father[i]==0)
		{
			root=i;
			break;
		}
	DFS(root,0);
	RMQ();
}

int LCA(int x,int y)
{
	int i,j;
	i=min(first[y],first[x]);
	if (i==first[x])
		j=first[y];
	else j=first[x];
	int s=log(j-i+1)/log(2);
	return h[rmq[i][s]]<h[rmq[j-(1<<s)+1][s]]? dfs[rmq[i][s]]:dfs[rmq[j-(1<<s)+1][s]];
}

int main ()
{
	//freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
	scanf("%d",&T);
	for (int i=1;i<=T;i++)
	{
		init();
		scanf("%d%d",&p,&q);
		printf("%d\n",LCA(p,q));
	}
	return 0;
}

• Re:为啥数组开大了反而WA，first数组开到25000ac，开到30000ac，30006就wa (1917) dcdcdc 2015-08-08 20:48:39
  • Re:为啥数组开大了反而WA，first数组开到25000ac，开到30000ac，30006就wa (2) zerQ 2019-08-17 22:05:12