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

## 为啥数组开大了反而WA，first数组开到25000ac，开到30000ac，30006就wa

Posted by qq836793 at 2014-04-06 21:52:08 on Problem 1330
```求大神指导啊感激不尽：
#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;
}```

Followed by: