include

include

include

include

include

include

using namespace std;

typedef struct _node { _node * prev; int value; int index; _node() { prev = NULL; value = 0; index = 0; } } NODE;

int GetPathFromRoot(int b, NODE *pNode, vector& nodes) { unsigned int i = 0; NODE *curNode = &pNode[b]; do { nodes.push_back(curNode); curNode = curNode->prev; } while (curNode != NULL); return 0; } int num = 0; int GetPath(int a, int b, NODE *pNode, vector& nodes) { //Get root to a vector rootA; vector rootB;

int *flag = new int[num];
memset(flag, 0, sizeof(int)*num);
GetPathFromRoot(a, pNode, rootA);    
GetPathFromRoot(b, pNode, rootB);


//merge rootA and rootB
int nA = 0;
int nB = 0;
int found = 0;
for (unsigned int i = 0; i < rootA.size(); i++)
{        
    flag[rootA[i]->index-1] = 1;
}
for (unsigned int i = 0; i < rootB.size(); i++)
{
    if (flag[rootB[i]->index-1] == 1)
    {
        nB = i;
        nA = rootB[i]->index;
        break;
    }
}

for (unsigned int i = 0; i < rootA.size(); i++)
{
    if (rootA[i]->index == nA)
        break;
    nodes.push_back(rootA[i]);
}
for (int i = nB; i >= 0; i--)
{
    nodes.push_back(rootB[i]);
}
delete [] flag;
return 0;

}

int FindSame(int w, int x, int y, int z, NODE *pNode) { int nMatch = 0; vector wxNode; vector yzNode; GetPath(w, x, pNode, wxNode); GetPath(y, z, pNode, yzNode);
for (unsigned int i = 0; i < wxNode.size(); i++) { for (unsigned int u = 0; u < yzNode.size(); u++) { if (wxNode[i]->value == yzNode[u]->value && (wxNode[i] != yzNode[u])) { nMatch++; } } } cout << nMatch << endl; return nMatch; }

int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */
int nodeNum = 0; int queryNum = 0; int i = 0; cin >> nodeNum; num = nodeNum; cin >> queryNum; NODE *pNode = new NODE[nodeNum];

for (i = 0; i < nodeNum; i++)
{
    cin >> pNode[i].value;
    pNode[i].index = i+1;       
}
int node1 = 0;
int node2 = 0;
bool fwd = true;
cin >> node1;
cin >> node2;
if (node1 == 1)
{
    fwd = true;
    pNode[node2-1].prev = &pNode[node1-1];   
}
else
{
    fwd = false;
    pNode[node1-1].prev = &pNode[node2-1];   
}


for (i = 1; i < nodeNum-1; i++)
{

    cin >> node1;
    cin >> node2;
    if (fwd)
        pNode[node2-1].prev = &pNode[node1-1];        
    else
        pNode[node1-1].prev = &pNode[node2-1]; 

}

//Tree is built

for (i = 0; i < queryNum; i++)
{
   int w = 0, x = 0, y = 0, z = 0;
    cin >> w;
    cin >> x;
    cin >> y;;
    cin >> z;
    FindSame(w-1, x-1, y-1, z-1, pNode);        
}
delete [] pNode;
return 0;

}

workts but timeout