Trees I Contest Editorial
Scoreboard
Stats
Q1 average: 77.7
Q2 average: 32.8
Q3 average: 30.8
Q4 average: 0 (yes)
Q5 average: 0.769
addictiontoworry
Problem 1
You have a tree of N nodes and N-1 edges.
Each edge has length ci
You are given Q queries on finding the shortest path from Xi to Yi while passing through node K where K is a fixed given node.
Subtask 1
Ai=i Bi=i+1 for all i in [1,N-1)
Notice that the tree is just a line in this case.
We can thus illustrate this on a number line and start answering the Q queries
Uh this solution is probably harder than the actual solution :clown
Subtask 1
Case 1: Xi < K < Yi
Distance will be Pre[Yi] - Pre[Xi -1]
�Where Pre[i] is the prefix sum of the weights of edges up to the number on the number line.
You can swap Xi and Yi to handle the case where Xi > K > Yi to handle the cases much easier
Xi
Yi
K
Subtask 1
Case 2: K < Xi < Yi
Distance will be Pre[Yi] - Pre[Xi -1] + Pre[Yi] - Pre[K-1]��This is because you go from Xi to K to Yi
Same case applies for K < Yi < Xi just swap them to make it easier to code
Xi
Yi
K
Subtask 1
Case 2: Xi < Yi < K
Now its Pre[Yi] - Pre[Xi-1] + Pre[K] - Pre[Xi-1]
As you go from Xi to K to Yi
Same idea applies for Yi < Xi < K just swap the 2
Xi
Yi
K
Subtask 1
Time complexity:
O(N+Q)
Ok ya that was way too unnecessarily complicated to the point I feel like it's harder than the actual question.
There is probably an easier way to solve this subtask but the idea is literally the same as the final solution
Subtask 2
N,Q <= 1000
For each query you run a dfs from node K to all nodes.
You then find the distances of the 2 furthest nodes from K and sum them up to get the longest path that contains K.
Time complexity:
O(NQ)
Subtask 3
Combine the precomputation idea with the dfs idea from subtask 1 and 2 respectively
You dfs from K once before all the queries and compute distances of K to all nodes.
Subtask 3
For each query your answer will be
distance[Xi]+distance[Yi] where distance[i] is the distance of i from node K
Time complexity :
O(N+Q)
leenbeeontree
Problem 2
Abridged statement :
You have a tree with N rooms
Start each traversal from room 1, visit all rooms at least once with as few traversals as possible
Problem 2
A bee spawns in a specific room before each traversal. You can collect it only during that traversal; otherwise, it disappears.
Determine the maximum number of bees you can collect while completing the map in the minimum number of traversals.
Subtask 1
You can only use 1 traversal, and the bee spawned will always be on this traversal.
Print 1.
Subtask 2
N<=1000
Observation 1:
The min number of traversals to visit every node is the number of leaves of the tree(excluding node 1 if it is a leaf).
Let the count be L
Subtask 2
We only keep track of the P_i where 1<=i<=L. The rest of the array we ignore.
Subtask 2
For each leaf we greedily “pair” it with the closest bee Pi that is an ancestor of the leaf li . “Pair” as in we collect the bee by traversing from 1 to that leaf.
Subtask 2
Proof:
Suppose this was not optimal. This means that li should get paired with some other pj or not get paired at all.
Subtask 2
Proof:
If li gets paired with some pj and another leaf lj pairs with pi this is equivalent to our greedy pairing as pj must be an ancestor of pi and therefore be able to pair with lj. If li should not get paired and lj should pair with pi, this will still provide an equivalent answer to our construction as we still gain a bee
Subtask 2
Thus for each leaf we go up the tree until we found the first bee available and pair them together. If we found a successful pair we increment the answer by 1
Since there are O(N) leaves and each node having up to O(N) nodes, such a solution will take O(N^2) to run
Subtask 3
For the full solution we can achieve everything in one dfs instead.
When doing a dfs we will go down a tree and then go back up the tree right?
Subtask 3
Recall solution in subtask 2 where we are trying to find the closest bee to each leaf to pair them together.
Here we can do something similar as we are returning back up from the dfs whenever we encounter a leaf.
1
3
4
7
9
8
11
10
0
2
5
6
12
1
3
4
7
9
8
11
10
0
2
5
6
12
1
3
4
7
9
8
11
10
0
2
5
6
12
1
3
4
7
9
8
11
10
0
2
5
6
12
1
3
4
7
9
8
11
10
0
2
5
6
12
1
3
4
7
9
8
11
10
0
2
5
6
12
Subtask 3
During the dfs we keep track of the leaves that are not paired as well as the number of times each bee spawns in each node.
If we first encounter a bee when returning back up from the tree, the leaf and the bee is paired and we obtained 1 more bee.
Subtask 3
As such we maintain the number of unpaired leaves and bees and start pairing the leaves and the bees as we traverse back up the tree and adding the number of paired bees and trees to our answer.
Note that if we run out of leaves we are unable to increment our answer further
Subtask 3
This solves the problem with a single dfs
Time complexity:
O(N)
lllontree
Problem 3
Abridged statement:
You have a tree with N nodes, each node has a value Ai
For every integer K in [1,N] print the longest increasing subsequence on the shortest simple path from node 1 to node K
Subtask 1
Ai=i Bi=i+1 for all i in [1,N-1)
Tree is just a line again.
Run NlogN LIS algorithm to obtain longest increasing subsequence ending at node K. (or element K since it is pretty much an array)
We then take a prefix max of the dp array and print out the prefix max.
Subtask 2
N<=500
For each path 1->k you build an array and run LIS algorithm on it.
Time complexity:
O(N^2 logN)
Subtask 3
Trainer skill issued and coded 1 lazy create segment tree with 3 dfs oops🤡.
Do note that one of your trainers explaining this forgot how the NlogN binary search LIS work and thus the explanation will be using a segment tree.
Subtask 3
Since a[i] <= 1e9 but N <=2e5 we can first discretize the values
So now our values of a[i] will just at most be in the range [1,N]
Note: I just typed a[i] instead of ai as it takes too long to type subscripts
Sample
Sample input:
a= [1, 2, 5, 3, 4, 6, 7, 3, 2, 4]
Same thing after discretization here
Sample
1
3
4
7
9
8
10
2
5
6
Subtask 3
Let dp[i] denote the LIS on the path from node 1 to node i ending at node i
We will write the values of a[i] in grey and dp[i] in green
Subtask 3
1
3
4
7
9
8
10
2
5
6
1
4
2
3
2
4
3
5
6
7
Subtask 3
Let dp[i] denote the LIS on the path from node 1 to node i ending at node i
It is assumed that you know how to code LIS
Subtask 3
1
3
4
7
9
8
10
2
5
6
1
3
2
2
2
4
3
3
4
5
Subtask 3
Now with the observation from subtask 1 we realise the answer for each node from 1 to k is the prefix max of the values along the path from 1 to k for all k.
But then in this specific test case just nice the prefix max values along each path is the value in the dp array so be careful to not bug by forgetting the prefix max part 🤡.
Subtask 3
Notice that when we arrange the tree like that it looks really like an array.
In fact at each junction it can form an array
Subtask 3
1
3
4
7
9
8
10
2
5
6
1
3
2
2
2
4
3
3
4
5
Subtask 3
Notice that when we arrange the tree like that it looks really like an array.
In fact at each junction it can form an array
Subtask 3
1
3
4
7
9
8
10
2
5
6
1
3
2
2
2
4
3
3
4
5
Subtask 3
Notice that when we arrange the tree like that it looks really like an array.
In fact at each junction it can form an array
1
3
4
7
9
8
10
2
5
6
1
3
2
2
2
4
3
3
4
5
Subtask 3
1
3
4
7
9
8
10
2
5
6
1
3
2
2
2
4
3
3
4
5
Subtask 3
As such we can just treat the tree as an array.
We do a dfs down all the way to a leaf. The path taken by the dfs will end up giving us an array. Using a segment tree we are able to compute dp[i] for all nodes i along that path
Our segment tree at pos a[i] stores value dp[i].
Subtask 3
So we dfs to our first leaf node. 1->2->3->4->5 and then we run LIS on this array
1
3
4
7
9
8
10
2
5
6
1
3
2
2
2
4
3
3
4
5
Subtask 3
After that we realise that we can still make use of our computed values from [1,3] thus we can perform rollback on the nodes and undo the changes we made on our segment tree due to nodes [4,5].
1
3
4
7
9
8
10
2
5
6
1
3
2
2
2
4
3
3
4
5
Subtask 3
We then traverse to node 7 via the dfs. Using the values in our dp array and segment tree, we are able compute dp values for LIS ending at each node for this path. We can then repeat this process at each junction.
Subtask 3
1
3
4
7
9
8
10
2
5
6
1
3
2
2
2
4
3
3
4
5
Subtask 3
To perform the rollback operations:
Before entering each junction, we store the temporary value of the segment tree at position a[i].
Subtask 3
We then continue dfs down the path and then return back to that junction as our segment tree gets its values adjusted throughout the path.
We then update the segment tree’s value at position a[i] back to the value before we went down the path and explore the new path taken.
This allows us to compute dp[i] for each node
Subtask 3
Lastly we just have to do a prefix max of the dp values for each path from 1 to K for every node K. This can be done with an extra dfs.
Finally we print the prefix max of the dp array for each node along the same path
Alternative solution
Store your typical LIS array, where dp_i stores the minimum end element of a increasing subsequence of length N.
Each time you add a element to the dp array as if you are doing array LIS. The only difference is you need to rollback.
To do that, you just need to set the dp value you modified back to its original.
richzhe
Q4
Subtask 1: Graph is line
You can hard core math this out but its kind of disgusting so we won’t go through it here.
Subtask 2: N <= 25
YOLO brute force O(N^4)
Subtask 3: N <= 100
Observation: The road you build should start from node 1.
Proof: It is never worse if you switch a road from not involving node 1 to involving node 1 as the distance will become shorter.
Subtask 3
Continue YOLO brute force but smarter, only try roads starting from 1.
O(N^3)
Subtask 4: N <= 1000
Let’s consider for each answer a, the maximum x such that the answer is <= a.
Then it is optimal to draw an edge from 1 to some node k. This means each node i must either have dep[i]<=a or dist(i,k)<=a-x.
Hence we must minimise “maximum value of dist(i,k) where dep[i] > a”.
Subtask 4
Consider the longest distance d between two vertices of depth>a.
Claim: the minimum possible “maximum value of dist(i,k)” is d/2.
Subtask 4
Claim: “maximum value of dist(i,k)” >= d/2.
Proof: Let the 2 vertices on the path of length d be x and y.
dist(x,k) + dist(y,k) >= d
So max(dist(x,k),dist(y,k))>=d/2.
Subtask 4
Claim: We can make “maximum value of dist(i,k)” = d/2.
Proof:
Let k be the midpoint of x to y.
Then dist(x,k) = dist(y,k) = d/2.
Subtask 4
Claim: We can make “maximum value of dist(i,k)” = d/2.
Proof: Let k be the midpoint of x to y.
Then dist(x,k) = dist(y,k) = d/2.
If dist(z,k) > d/2, then either x, k, z or y, k, z are “collinear”.
If x, k, z are collinear, dist(x,z)=dist(x,k)+dist(k,z)>d. Contradiction.
Subtask 4
This means that we want to find the longest distance d between two vertices of depth>a and check if ceil(d/2)+x<=a.
Basically we choose to build (1,k) where k is the midpoint of the diameter(or one of the midpoints if the diameter has even number of nodes).
Subtask 4
Proof: Suppose there is a node i where dep[i]>a such that it does not satisfy dist(i,k)+x<=a.
This means dist(i,k)>ceil(d/2) which means a new diameter should be formed.
Subtask 4
Hence, for each a we just need to find the maximum distance between two nodes of depth > a.
This can be done in O(N) time for each a in this subtask, the same way you compute diameter.
Subtask 4
We can therefore calculate the maximum x for each a.
Hence we can calculate the maximum a for each x.
Subtask 4
As x increases answer a also increases hence we can maintain a pointer tracking the answer a and check if we need to increase a each time.
If ceil(f[a]/2)+x>a then we need to increase a, where f[a] is the max distance array previously computed.
Subtask 5
Now we need to optimize the computation of f.
Lowkey it is kind of ooga booga and big brain so i will just give the method and explain why it works.
The motivation is the dp diameter calculation method. Sorry lab 1
Subtask 5
Let a and b be the depths of the deepest leaves in the subtree of v.
We update f_{b-1}=max(f_{b-1},a+b-2dep[v]).
Then after we do this for all v, we run a suffix maximum
Subtask 5
Suppose it doesn’t work. Let a be the largest a such that the f[a] is wrong.
This means there exists some u,v which has dep[u]>a, dep[v]>a and dist(u,v)>f[a].
Subtask 5
We see that either dep[u]=a+1 or dep[v]=a+1 as otherwise there would be a bigger a where the answer is wrong.
WLOG let dep[u]=a+1
Subtask 5
Let L=lca(u,v). When we do the processing for L, if b=dep[u]+1, we must have accounted for this (u,v) pair already.
Otherwise, b>dep[u]+1 and hence there is already a pair that has longer distance and we don’t need to care about this (u,v) pair.
Subtask 5
Hence, we just need to keep track of the two deepest leaves for each subtree and use the formula accordingly. Then run the suffix max and we get our f.
Then we use subtask 4 solution to solve this problem in O(N).
nomorebp
Abridged statement
In each operation you can delete a set of vertices from the same connected component such that there is no black node and pink node both in the set.
Find the minimum number of operations to delete the whole tree.
Subtask 1
Brute force
Subtask 2
We reduce the tree to an array problem.
We observe we can always delete connected subarrays of the same color.
Hence we can compress the array to b_i where b_i!=b_i+1
Subtask 2
Suppose this compressed array has length k.
If k is odd we can keep on deleting the start and end of the array in one operation until no more.
If k is even, we just spend one operation deleting one end and then do the k is odd algorithm.
Our answer is floor(k/2)+1
Subtask 3
If you delete the grey colors from the array and run the same solution as subtask 2 it actually just works.
This is because you can just set the grey to whatever color it is being bunched together with and it works.
Subtask 4
Let’s set the weight of edge uv to be 0 if a[u]=a[v].
Let k be the diameter of this tree.
Our answer is floor(k/2)+1.
Subtask 4
This number of operations is necessary as if we can do in lesser => we can do the line subtask in lesser operations also which is not possible.
We alternate between deleting black and pink leaves with the same color and we can see it will be the correct number of operations.
Subtask 5
If you can’t implement subtask 6 in good time complexity but your brain is massive enough heres some free points.
Subtask 6
In subtask 4, we alternated between deleting black and pink leaves.
Now we have grey leaves. We can actually just try the same thing, except we need to figure out which color to start with.
Subtask 6
We can actually just try both.
All in all, the algorithm is just try starting with deleting all pink/grey leaves, then black/grey then etc.
Then try starting with black/grey, then pink/grey etc.
Subtask 6
This works because our algorithm is equivalent to choosing a coloring for the grey leaves based on the first vertex we delete.
Our coloring will never make the tree worse than the initial tree because we can make the same removals.
Subtask 6
Our diameter idea still holds and hence our answer from this greedy removal is necessary.
Conclusion
The last 2 problems are very dank and require some thought so if you don’t get it on the first try think about it a bit more and maybe there will be a AHA OMY SKIBIDI moment.