Description

Story

(The following story is irrelevant to the problem description.)

Red Cape Flying Cat and penguins are playing a game on a tree. The penguins each stand on a different node. To prevent them from falling off the tree, Red Cape Flying Cat wants to find the lowest common ancestor of the penguins, so that he can protect both of them at once and make sure neither of them stays airborne for too long.

Problem Statement

Given a rooted binary tree with n nodes, where node 1 is the root. Each node has at most 2 children. The depth of the root is defined as 1, and the depth of any other node is the depth of its parent plus one.

Output the depth of every node, and answer q queries. Each query gives two nodes u and v; output their Lowest Common Ancestor (LCA) — the node that is an ancestor of both u and v and has the greatest depth.

Note that a node is considered an ancestor of itself.

You may use the following template to solve this problem:

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int idx;
    struct Node *parent, *leftChild, *rightChild;
    int dep, vis;
} Node;

Node* tree[10005];

int main() {
    // init
    for (int i = 0; i < 10005; i++) {
        tree[i] = (Node*)malloc(sizeof(Node));
        tree[i]->idx = i;
        tree[i]->parent = NULL;
        tree[i]->leftChild = NULL;
        tree[i]->rightChild = NULL;
        tree[i]->dep = 0;
        tree[i]->vis = 0;
    }
}

Explanation

The tree has 4 nodes. From the parent array 1 1 2, we know:

• Node 2's parent is node 1
• Node 3's parent is node 1
• Node 4's parent is node 2

So the tree looks like this:

    1        (depth 1)
   / \
  2   3      (depth 2)
  |
  4          (depth 3)

The depth output is 1 2 2 3.

Query 1: LCA(4, 4) = 4
The LCA of a node with itself is the node itself.

Query 2: LCA(2, 4) = 2
The ancestors of node 4 are: 4, 2, 1. The ancestors of node 2 are: 2, 1. The deepest common ancestor is node 2.

Query 3: LCA(4, 3) = 1
The ancestors of node 4 are: 4, 2, 1. The ancestors of node 3 are: 3, 1. The deepest common ancestor is node 1.

Input

n
p2 p3 ... pn
q
u1 v1
u2 v2
...
uq vq

• n: number of nodes in the tree
• pi: parent of node i, for i = 2, 3, ..., n
• q: number of queries
• ui, vi: the two nodes of the i-th query
• If n = 1, the second line is empty.

Constraints

• 1 <= n <= 10^4
• 1 <= pi <= n, pi != i
• The input is guaranteed to form a tree rooted at node 1
• The tree is guaranteed to be a binary tree (each node has at most 2 children)
• 1 <= q <= 10^4
• 1 <= ui, vi <= n

Output

d1 d2 d3 ... dn
lca1
lca2
...
lcaq

• di: depth of node i
• lcai: the LCA node of the i-th query

Note that there must be no trailing space after the last depth value.

Sample Input  Download

Sample Output  Download

Discuss