> 求大神指导啊感激不尽：
> #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 (2) zerQ 2019-08-17 22:05:12