Tree Algorithms Jul 27, 2025
Problem A. Subordinates
Time Limit 1000 ms
Mem Limit 524288 kB
Given the structure of a company, your task is to calculate for each employee the number
of their subordinates.
Input
The first input line has an integer n: the number of employees. The employees are
numbered 1, 2, … , n, and employee 1 is the general director of the company.
After this, there are n − 1 integers: for each employee 2, 3, … , n their direct boss in the
company.
Output
Print n integers: for each employee 1, 2, … , n the number of their subordinates.
Constraints
1 ≤ n ≤ 2 ⋅ 105
Example
Input Output
5 4 1 1 0 0
1 1 2 3
Page 1 of 19
-
Tree Algorithms Jul 27, 2025
Problem B. Tree Matching
Time Limit 1000 ms
Mem Limit 524288 kB
You are given a tree consisting of n nodes.
A matching is a set of edges where each node is an endpoint of at most one edge. What is
the maximum number of edges in a matching?
Input
The first input line contains an integer n: the number of nodes. The nodes are numbered
1, 2, … , n.
Then there are n − 1 lines describing the edges. Each line contains two integers a and b:
there is an edge between nodes a and b.
Output
Print one integer: the maximum number of pairs.
Constraints
1 ≤ n ≤ 2 ⋅ 105
1 ≤ a, b ≤ n
Example
Input Output
5 2
1 2
1 3
3 4
3 5
Explanation: One possible matching is (1, 2) and (3, 4).
Page 2 of 19
-
Tree Algorithms Jul 27, 2025
Problem C. Tree Diameter
Time Limit 1000 ms
Mem Limit 524288 kB
You are given a tree consisting of n nodes.
The diameter of a tree is the maximum distance between two nodes. Your task is to
determine the diameter of the tree.
Input
The first input line contains an integer n: the number of nodes. The nodes are numbered
1, 2, … , n.
Then there are n − 1 lines describing the edges. Each line contains two integers a and b:
there is an edge between nodes a and b.
Output
Print one integer: the diameter of the tree.
Constraints
1 ≤ n ≤ 2 ⋅ 105
1 ≤ a, b ≤ n
Example
Input Output
5 3
1 2
1 3
3 4
3 5
Explanation: The diameter corresponds to the path 2 → 1 → 3 → 5.
Page 3 of 19
-
Tree Algorithms Jul 27, 2025
Problem D. Tree Distances I
Time Limit 1000 ms
Mem Limit 524288 kB
You are given a tree consisting of n nodes.
Your task is to determine for each node the maximum distance to another node.
Input
The first input line contains an integer n: the number of nodes. The nodes are numbered
1, 2, … , n.
Then there are n − 1 lines describing the edges. Each line contains two integers a and b:
there is an edge between nodes a and b.
Output
Print n integers: for each node 1, 2, … , n, the maximum distance to another node.
Constraints
1 ≤ n ≤ 2 ⋅ 105
1 ≤ a, b ≤ n
Example
Input Output
5 2 3 2 3 3
1 2
1 3
3 4
3 5
Page 4 of 19
-
Tree Algorithms Jul 27, 2025
Problem E. Tree Distances II
Time Limit 1000 ms
Mem Limit 524288 kB
You are given a tree consisting of n nodes.
Your task is to determine for each node the sum of the distances from the node to all other
nodes.
Input
The first input line contains an integer n: the number of nodes. The nodes are numbered
1, 2, … , n.
Then there are n − 1 lines describing the edges. Each line contains two integers a and b:
there is an edge between nodes a and b.
Output
Print n integers: for each node 1, 2, … , n, the sum of the distances.
Constraints
1 ≤ n ≤ 2 ⋅ 105
1 ≤ a, b ≤ n
Example
Input Output
5 6 9 5 8 8
1 2
1 3
3 4
3 5
Page 5 of 19
-
Tree Algorithms Jul 27, 2025
Problem F. Company Queries I
Time Limit 1000 ms
Mem Limit 524288 kB
A company has n employees, who form a tree hierarchy where each employee has a boss,
except for the general director.
Your task is to process q queries of the form: who is employee x's boss k levels higher up
in the hierarchy?
Input
The first input line has two integers n and q : the number of employees and queries. The
employees are numbered 1, 2, … , n, and employee 1 is the general director.
The next line has n − 1 integers e2 , e3 , … , en : for each employee 2, 3, … , n their boss.
Finally, there are q lines describing the queries. Each line has two integers x and k : who is
employee x's boss k levels higher up?
Output
Print the answer for each query. If such a boss does not exist, print −1.
Constraints
1 ≤ n, q ≤ 2 ⋅ 105
1 ≤ ei ≤ i − 1
1≤x≤n
1≤k≤n
Example
Input Output
5 3 3
1 1 3 3 1
4 1 -1
4 2
4 3
Page 6 of 19
-
Tree Algorithms Jul 27, 2025
Problem G. Company Queries II
Time Limit 1000 ms
Mem Limit 524288 kB
A company has n employees, who form a tree hierarchy where each employee has a boss,
except for the general director.
Your task is to process q queries of the form: who is the lowest common boss of
employees a and b in the hierarchy?
Input
The first input line has two integers n and q : the number of employees and queries. The
employees are numbered 1, 2, … , n, and employee 1 is the general director.
The next line has n − 1 integers e2 , e3 , … , en : for each employee 2, 3, … , n their boss.
Finally, there are q lines describing the queries. Each line has two integers a and b: who is
the lowest common boss of employees a and b?
Output
Print the answer for each query.
Constraints
1 ≤ n, q ≤ 2 ⋅ 105
1 ≤ ei ≤ i − 1
1 ≤ a, b ≤ n
Example
Input Output
5 3 3
1 1 3 3 1
4 5 1
2 5
1 4
Page 7 of 19
-
Tree Algorithms Jul 27, 2025
Problem H. Distance Queries
Time Limit 1000 ms
Mem Limit 524288 kB
You are given a tree consisting of n nodes.
Your task is to process q queries of the form: what is the distance between nodes a and b?
Input
The first input line contains two integers n and q : the number of nodes and queries. The
nodes are numbered 1, 2, … , n.
Then there are n − 1 lines describing the edges. Each line contains two integers a and b:
there is an edge between nodes a and b.
Finally, there are q lines describing the queries. Each line contains two integer a and b:
what is the distance between nodes a and b?
Output
Print q integers: the answer to each query.
Constraints
1 ≤ n, q ≤ 2 ⋅ 105
1 ≤ a, b ≤ n
Example
Input Output
5 3 1
1 2 3
1 3 2
3 4
3 5
1 3
2 5
1 4
Page 8 of 19
-
Tree Algorithms Jul 27, 2025
Problem I. Counting Paths
Time Limit 1000 ms
Mem Limit 524288 kB
You are given a tree consisting of n nodes, and m paths in the tree.
Your task is to calculate for each node the number of paths containing that node.
Input
The first input line contains integers n and m: the number of nodes and paths. The nodes
are numbered 1, 2, … , n.
Then there are n − 1 lines describing the edges. Each line contains two integers a and b:
there is an edge between nodes a and b.
Finally, there are m lines describing the paths. Each line contains two integers a and b:
there is a path between nodes a and b.
Output
Print n integers: for each node 1, 2, … , n, the number of paths containing that node.
Constraints
1 ≤ n, m ≤ 2 ⋅ 105
1 ≤ a, b ≤ n
Example
Input Output
5 3 3 1 3 1 1
1 2
1 3
3 4
3 5
1 3
2 5
1 4
Page 9 of 19
-
Tree Algorithms Jul 27, 2025
Problem J. Subtree Queries
Time Limit 1000 ms
Mem Limit 524288 kB
You are given a rooted tree consisting of n nodes. The nodes are numbered 1, 2, … , n,
and node 1 is the root. Each node has a value.
Your task is to process following types of queries:
1. change the value of node s to x
2. calculate the sum of values in the subtree of node s
Input
The first input line contains two integers n and q : the number of nodes and queries. The
nodes are numbered 1, 2, … , n.
The next line has n integers v1 , v2 , … , vn : the value of each node.
Then there are n − 1 lines describing the edges. Each line contans two integers a and b:
there is an edge between nodes a and b.
Finally, there are q lines describing the queries. Each query is either of the form "1 s x" or
"2 s".
Output
Print the answer to each query of type 2.
Constraints
1 ≤ n, q ≤ 2 ⋅ 105
1 ≤ a, b, s ≤ n
1 ≤ vi , x ≤ 109
Example
Page 10 of 19
-
Tree Algorithms Jul 27, 2025
Input Output
5 3 8
4 2 5 2 1 10
1 2
1 3
3 4
3 5
2 3
1 5 3
2 3
Page 11 of 19
-
Tree Algorithms Jul 27, 2025
Problem K. Path Queries
Time Limit 1000 ms
Mem Limit 524288 kB
You are given a rooted tree consisting of n nodes. The nodes are numbered 1, 2, … , n,
and node 1 is the root. Each node has a value.
Your task is to process following types of queries:
1. change the value of node s to x
2. calculate the sum of values on the path from the root to node s
Input
The first input line contains two integers n and q : the number of nodes and queries. The
nodes are numbered 1, 2, … , n.
The next line has n integers v1 , v2 , … , vn : the value of each node.
Then there are n − 1 lines describing the edges. Each line contains two integers a and b:
there is an edge between nodes a and b.
Finally, there are q lines describing the queries. Each query is either of the form "1 s x" or
"2 s".
Output
Print the answer to each query of type 2.
Constraints
1 ≤ n, q ≤ 2 ⋅ 105
1 ≤ a, b, s ≤ n
1 ≤ vi , x ≤ 109
Example
Page 12 of 19
-
Tree Algorithms Jul 27, 2025
Input Output
5 3 11
4 2 5 2 1 8
1 2
1 3
3 4
3 5
2 4
1 3 2
2 4
Page 13 of 19
-
Tree Algorithms Jul 27, 2025
Problem L. Path Queries II
Time Limit 1000 ms
Mem Limit 524288 kB
You are given a tree consisting of n nodes. The nodes are numbered 1, 2, … , n. Each node
has a value.
Your task is to process following types of queries:
1. change the value of node s to x
2. find the maximum value on the path between nodes a and b.
Input
The first input line contains two integers n and q : the number of nodes and queries. The
nodes are numbered 1, 2, … , n.
The next line has n integers v1 , v2 , … , vn : the value of each node.
Then there are n − 1 lines describing the edges. Each line contains two integers a and b:
there is an edge between nodes a and b.
Finally, there are q lines describing the queries. Each query is either of the form "1 s x" or
"2 a b".
Output
Print the answer to each query of type 2.
Constraints
1 ≤ n, q ≤ 2 ⋅ 105
1 ≤ a, b, s ≤ n
1 ≤ vi , x ≤ 109
Example
Page 14 of 19
-
Tree Algorithms Jul 27, 2025
Input Output
5 3 4 3
2 4 1 3 3
1 2
1 3
2 4
2 5
2 3 5
1 2 2
2 3 5
Page 15 of 19
-
Tree Algorithms Jul 27, 2025
Problem M. Distinct Colors
Time Limit 1000 ms
Mem Limit 524288 kB
You are given a rooted tree consisting of n nodes. The nodes are numbered 1, 2, … , n,
and node 1 is the root. Each node has a color.
Your task is to determine for each node the number of distinct colors in the subtree of the
node.
Input
The first input line contains an integer n: the number of nodes. The nodes are numbered
1, 2, … , n.
The next line consists of n integers c1 , c2 , … , cn : the color of each node.
Then there are n − 1 lines describing the edges. Each line contains two integers a and b:
there is an edge between nodes a and b.
Output
Print n integers: for each node 1, 2, … , n, the number of distinct colors.
Constraints
1 ≤ n ≤ 2 ⋅ 105
1 ≤ a, b ≤ n
1 ≤ ci ≤ 109
Example
Input Output
5 3 1 2 1 1
2 3 2 2 1
1 2
1 3
3 4
3 5
Page 16 of 19
-
Tree Algorithms Jul 27, 2025
Problem N. Finding a Centroid
Time Limit 1000 ms
Mem Limit 524288 kB
Given a tree of n nodes, your task is to find a centroid, i.e., a node such that when it is
appointed the root of the tree, each subtree has at most ⌊n/2⌋ nodes.
Input
The first input line contains an integer n: the number of nodes. The nodes are numbered
1, 2, … , n.
Then there are n − 1 lines describing the edges. Each line contains two integers a and b:
there is an edge between nodes a and b.
Output
Print one integer: a centroid node. If there are several possibilities, you can choose any of
them.
Constraints
1 ≤ n ≤ 2 ⋅ 105
1 ≤ a, b ≤ n
Example
Input Output
5 3
1 2
2 3
3 4
3 5
Page 17 of 19
-
Tree Algorithms Jul 27, 2025
Problem O. Fixed-Length Paths I
Time Limit 1000 ms
Mem Limit 524288 kB
Given a tree of n nodes, your task is to count the number of distinct paths that consist of
exactly k edges.
Input
The first input line contains two integers n and k : the number of nodes and the path
length. The nodes are numbered 1, 2, … , n.
Then there are n − 1 lines describing the edges. Each line contains two integers a and b:
there is an edge between nodes a and b.
Output
Print one integer: the number of paths.
Constraints
1 ≤ k ≤ n ≤ 2 ⋅ 105
1 ≤ a, b ≤ n
Example
Input Output
5 2 4
1 2
2 3
3 4
3 5
Page 18 of 19
-
Tree Algorithms Jul 27, 2025
Problem P. Fixed-Length Paths II
Time Limit 1000 ms
Mem Limit 524288 kB
Given a tree of n nodes, your task is to count the number of distinct paths that have at
least k1 and at most k2 edges.
Input
The first input line contains three integers n, k1 and k2 : the number of nodes and the path
lengths. The nodes are numbered 1, 2, … , n.
Then there are n − 1 lines describing the edges. Each line contains two integers a and b:
there is an edge between nodes a and b.
Output
Print one integer: the number of paths.
Constraints
1 ≤ k1 ≤ k2 ≤ n ≤ 2 ⋅ 105
1 ≤ a, b ≤ n
Example
Input Output
5 2 3 6
1 2
2 3
3 4
3 5
Page 19 of 19
-
