| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11566 | Tree distance |
|
| 11586 | linked list-insert and remove |
|
Description
Calculate the distance between two nodes.
Input
For each case, the first line contains a positive integer N (1 <= N <= 1000), denoting the number of node in the tree (labeled from 1 to N). The second line contains exactly N numbers. The first number denotes the parent of node 1, and the second number denotes the parent of node 2 ..., etc. The root will be labeled as -1.
For example, sample input
3
-1 1 1
node 1 is root.
The parent of node 2 is node 1.
The parent of node 3 is node 1.
Then follows multiple lines of query (query < 10000). Each line contains two positive integers A and B. The query is terminated by two zeros.
Do not assume it is a binary tree.
Output
For each case a line, print the case number first, then output the distance between A and B for each query. Each answer should be separated by a single space.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
This problem will ask you to do some operations on a list. These operations contains insert, print, remove and show. The position of first node is 0.
Input
The input consist of a number of operations. The first line specifies a non-negative integer N that specifies the number of operations. Each operations (I, P, R and S) are separated by a newline character (\n).
I stands for “insert”, following by a non-negative integer (insert position, non-negative integer) and a non-negative integer (insert value, 0<=insert value<20). Insert a node at insert position with insert value.
If insert position is greater than or equal to the length of the list, treat the insert position as the next position of the last position at the list.
For example, input is
I 0 0
I 1 1
S
Output should be
0 1
P stands for “print”, following by a non-negative integer (print position). Print the value of the node at print position.
If print position is greater than or equal to the length of the list, treat the input position as the last position at the list. If the print position of P does not have a node, do not print anything.
R stands for “remove”, following by a non-negative integer (remove value). Remove the nodes in the list with the value that is equal to remove value.
S stands for “show”. Print the value of all nodes in the list. Separate every prints by a whitespace character. If the list is empty, do not print anything.
For example, input is
3
P 2
R 1
S
Output should be nothing.
Output
Print a space after doing P or S operations (if P or S has printed something).