Description
Important Note
Before submitting your code:
- You must submit implementations for all functions (the function body may be empty).
- You must submit all header files you use.
Otherwise, you may receive a Compile Errorr.
Story
(The following story is irrelevant to the problem description.)
Red Cape Flying Cat spotted the penguins playing in the trees and happily joined in. As they leaped from branch to branch together, Red Cape Flying Cat grew curious: from any position in the tree, how high up can you reach by jumping in powers of two? Being a CS student, he only cares about which node you land on after jumping exactly 2^j steps upward. Since he is still busy playing with the penguins, please write a program to help him figure it out.
Problem Statement
This is a partial judge problem.
In a single test case, the total number of function calls will not exceed 5*10^3.
You are given a rooted binary tree with n nodes (1 <= n <= 10^4), numbered 1 to n. Node 1 is always the root.
Each node is defined as the following structure:
typedef struct Node {
int idx;
struct Node *parent, *leftChild, *rightChild;
int vis; // for auxiliary use, initialized to 0
int dep; // pre-filled by main.c
int subtreeSize; // TODO: filled by find_subtree_size
struct Node* jump[14]; // TODO: filled by build_jump
} Node;
The main.c reads the input and constructs the tree by setting parent, leftChild, and rightChild for each node. Children are always assigned to the left child first — a node will never have a right child without also having a left child.
The dep field of every node is pre-filled by main.c before any function is called.
You need to implement the following 4 functions:
The following tree with n = 5 is used as a reference for all examples below:
1. Find LCA
Goal
Your goal is to implement a function that, given two nodes u and v, returns a pointer to their Lowest Common Ancestor (LCA):
Node* find_lca(Node* u, Node* v);
The LCA of nodes u and v is the deepest node that is an ancestor of both u and v. Node a is an ancestor of node b if a lies on the path from b to the root (inclusive of a and b themselves). If u == v, return u.
Constraint
1 <= u->idx, v->idx <= n- Before this function is called, the
visfield of every node is guaranteed to be0.
Example
Using the same tree (n = 5):
code:
printf("lca: %d\n", find_lca(tree[4], tree[5])->idx);
printf("lca: %d\n", find_lca(tree[4], tree[3])->idx);
printf("lca: %d\n", find_lca(tree[3], tree[3])->idx);
output:
lca: 2
lca: 1
lca: 3
explanation:
2. Find Subtree Size
Goal
Your goal is to implement a function that computes the subtree size of every node in the tree:
void find_subtree_size(Node* root);
The subtree size of a node is defined as: the number of nodes in the subtree rooted at that node, including the node itself. Store the subtree size of each node in its subtreeSize field.
This function is called at most once per test case.
Constraint
- When called,
rootis alwaystree[1]
Example
Using the same tree (n = 5):
code:
find_subtree_size(tree[1]);
printf("subtree size: [%d, %d, %d, %d, %d]\n",
tree[1]->subtreeSize, tree[2]->subtreeSize, tree[3]->subtreeSize,
tree[4]->subtreeSize, tree[5]->subtreeSize);
output:
subtree size: [5, 3, 1, 1, 1]
explanation:
3. Find Distance
Goal
Your goal is to implement a function that, given two nodes u and v, returns the distance between them:
int find_distance(Node* u, Node* v);
The distance between u and v is the number of edges on the unique path connecting them. If u == v, return 0.
Constraint
1 <= u->idx, v->idx <= n- The
depfield of every node is guaranteed to be pre-filled before this function is called. - Before this function is called, the
visfield of every node is guaranteed to be0.
Example
Using the same tree (n = 5):
code:
printf("distance: %d\n", find_distance(tree[4], tree[5]));
printf("distance: %d\n", find_distance(tree[4], tree[3]));
printf("distance: %d\n", find_distance(tree[3], tree[3]));
output:
distance: 2
distance: 3
distance: 0
explanation:
4. Build Jump Table
Goal
Your goal is to implement a function that builds the binary lifting table:
void build_jump(Node* tree[], int n);
The binary lifting table of a node is defined as: node->jump[j] is the node reached by going up 2^j steps from that node, for 0 <= j < 14. Store the result in node->jump[j] for every node tree[1] through tree[n]. If going up 2^j steps would pass the root, the result is the root itself. In particular, tree[1]->jump[j] = tree[1] for all j >= 0.
This function is called at most once per test case.
Constraint
1 <= n <= 10^4
Example
Using the same tree (n = 5):
code:
build_jump(tree, 5);
printf("jump table:\n");
for (int i = 1; i <= 5; i++) {
for (int j = 0; j < 14; j++)
printf("%d%c", tree[i]->jump[j]->idx, j < 13 ? ' ' : '\n');
}
output:
jump table:
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1 1 1 1 1
explanation:
Subtask
Input
The first line contains a single integer n (1 <= n <= 10^4), the number of nodes in the binary tree.
The second line contains n - 1 space-separated integers: par[2] par[3] ... par[n], where par[i] is the parent of node i. (If n = 1, this line is omitted.)
Guarantee: Children are always assigned to the left child first — a node will never have a right child without also having a left child.
The third line contains a single integer q (1 <= q <= 5*10^3), the total number of function calls.
Each of the following q operations is formatted as follows:
find_lca
1 <u> <v>
find_subtree_size
2
find_distance
3 <u> <v>
build_jump
4
Guarantee: Operations 2 and 4 each appear at most once in the input.
Output
The output for each function call is as follows:
find_lca
lca: <result>
find_subtree_size
subtree size: [<tree[1]->subtreeSize>, <tree[2]->subtreeSize>, ..., <tree[n]->subtreeSize>]
find_distance
distance: <result>
build_jump
jump table:
<tree[1]->jump[0]->idx> <tree[1]->jump[1]->idx> ... <tree[1]->jump[13]->idx>
<tree[2]->jump[0]->idx> <tree[2]->jump[1]->idx> ... <tree[2]->jump[13]->idx>
...
<tree[n]->jump[0]->idx> <tree[n]->jump[1]->idx> ... <tree[n]->jump[13]->idx>