/*
if node in the first section then P[node]=1
if node in the beginning of some section then P[node]=T[node]
if none then P[node]=P[T[node]]
*/
#define SIZE 102
int T[SIZE];//the father of node i in the tree
int L[SIZE];//level of the node i
int P[SIZE];//lowest ancestor of the node from the prev. section
//pre-process p using DFS
int N;
int nr;//sqrt(H)
list<int>Child[SIZE];
list<int>::iterator it;
void dfs(int node)
{
if(L[node]<nr)
P[node]=1;
else
{
if(L[node]%nr==0)//SEG-FAULT here node=6316144
P[node]=T[node];
else
P[node]=P[T[node]];
}
//for each son k of node
for(it=Child[node].begin();it!=Child[node].end();it++)
{
dfs(*it);
}
}
//here's the code to initialize L and nr
int initialize()
{
//initialize the L array and the nr value by finding out value of H
int root,i;
for(i=1;i<=N;i++)
{
if(T[i]==-1)
{
root=i;
break;
}
}
queue<int>Q;
queue<int>t;
t.push(root);
int s,l=0;//nodes at the same level
//process all the nodes in the Q at this moment
while(!t.empty())
{
while(!t.empty())
{
s=t.front();
t.pop();
L[s]=l;
Q.push(s);
}
while(!Q.empty())
{
s=Q.front();
Q.pop();
for(it=Child[s].begin();it!=Child[s].end();it++)//children of node s
t.push(*it);
}
l++;
}
int height=l;
nr=sqrt(height);
return root;
}
//here's the code to obtain the tree
void getTree()
{
// printf("\nHow many nodes?");
scanf("%d",&N);
//printf("\nNow enter the tree as parent #children children");
int i,n,p,j,c;
for(i=0;i<=N;i++)
T[i]=-1;//all the nodes do not have parents
for(i=0;i<N;i++)
{
scanf("%d%d",&p,&n);
for(j=0;j<n;j++)
{
scanf("%d",&c);
Child[p].push_back(c);//child is pushed in the correct parent's list
T[c]=p;//parent is updated
}
}
}
上記は、LCA (Lowest Common Ancestor) 問題を解決するために P 配列を設定する単純なコードです (topcoder の記事から)。nr=sqrt(H) (別の関数を使用して評価)。リスト Child のグローバル配列には、ノードの子のインデックスが含まれます。ノードがリーフの場合、一部のリストは空です。L 配列には、BFS を使用して初期化されたノード (0 ベース) のレベルが含まれています (これは正しいです)。問題は、入力が与えられ、dfs(r)(ルート)が呼び出されるたびにセグメンテーション違反が発生し、示された行のノードの値が 6316144 と表示されることです。何が問題なのか理解できません...