Jon.Snow's blog

By Jon.Snow, 12 months ago, In English

Hello Codeforces,

CSES is a nice collection of classical CP problems which encourages you to learn a lot of basic and advanced concepts. Having editorials would help people to not get stuck on a problem for long. Here are my solutions to the tree section of the problem-set. Looking forward to read corrections/feedback/better solutions in the comment section. Happy coding!

Subordinates

This can be solved using basic DP approach in linear time.
$$$subordinates[u] = \sum\limits_{v:children[u]}^{} subordinates[v]$$$ where v is a child of u

Code

Tree Matching

This problem can be reduced to maximum bipartite matching problem but first we need to split the tree into a bipartite graph. One way to do that is to put all nodes at even depth in the first group and odd ones in the other group. Such a splitting will make sure that we do not have any edges within the same group.

Next, we can use Hopkraft Karp algorithm to find the maximum matching in the bipartite graph created.

Code

Tree Diameter

This is a classical problem having multiple solutions.

One easy to implement solution is using 2 Breadth First Searches (BFS). Start a BFS with a random node and store the last node encountered before search ends. This last node will definitely be one of the ends of the diameter (Why?). Now run a second BFS from this node and you will end on the other end of the diameter.

Code

Tree Distances I

For each node, we want to calculate maximum distance to another node. Previously we saw that that if we start a BFS from any node, we end up on either of the diametric end. We can use this fact to efficiently compute the answer. Let's calculate distances of each node from both the ends of the diameter. Then maximum distance of each node can be calculated as:

max_distance[u] = max(distance_from_diametric_end1[u], distance_from_diametric_end2[u])
Code

Tree Distances II

We can solve this problem using in-out DP on trees.
$$$in[u]:$$$ sum of distances from u to each node in subtree rooted at u
$$$out[u]:$$$ sum of distances from u to each node excluding the subtree rooted at u

Now, ans[u] = in[u] + out[u]

Calculating $$$in[u]$$$ is quite straightforward. Suppose we want to calculate the sum of distances starting at node u and ending at any node in subtree rooted at v. We can use the pre-calculated value for v and separately add the contribution created by edge $$$u\rightarrow v$$$. This extra quantity will be the subtree size of u. Then we can repeat the process for each child of u.

$$$in[u] = \sum\limits{}{}in[v] + sub[v]$$$ where v is a child of u

To calculate $$$out[u]$$$, first let's calculate the contribution of parent of u. We can use out[par] and add the difference created by the edge $$$u \rightarrow par_u$$$ which is n-sub[par]+1. Next, we add the contribution of each sibling of u: in[sib] + sub[sib]*2.
Finally we have the following formula:

$$$out[u] = out[par] + (n-sub[par] + 1) + (\sum\limits_{sib}{} in[sib] + sub[sib]*2) - (in[u] + sub[u]*2)$$$

Code

Company Queries I

We can solve this problem using binary-lifting technique for finding ancestors in a tree.

For each node x given in a query, we just need to find the $$$k^{th}$$$ ancestor of a given node. We can initialise ans = x and keep lifting our ans for every $$$i^{th}$$$ bit set in k: ans = jump[i][ans] where $$$jump[i][j]$$$ holds $$$i^{th}$$$ ancestor of node $$$j$$$

Code

Company Queries II

This is the classical problem of finding Lowest Common Ancestor which can be solved in multiple ways. One of the common ways is to use binary-lifting which requires $$$O(nlog(n))$$$ preprocessing and $$$O(logn)$$$ per query.

Code

Distance Queries

Distance between node u and v can be calculated as $$$depth[u] + depth[v] - 2*depth[LCA(u,v)]$$$.
LCA of (u,v) can be calculated using binary-lifting approach in $$$O(logn)$$$ per query.

Code

Counting Paths

This problem can be solved using prefix sum on trees.

For every given path $$$u \rightarrow v$$$, we do following changes to the prefix array.

prefix[u]++
prefix[v]++
prefix[lca]--
prefix[parent[lca]]--

Next, we run a subtree summation over entire tree which means every node now holds the number of paths that node is a part of. This method is analogous to range update and point query in arrays, when all updates are preceded by queries.
$$$prefix[u] = \sum\limits_{v:children[u]}^{} prefix[v]$$$

Code

Subtree Queries

This problem can be solved by flattening the tree to an array and then building a fenwick tree over flattened array.

Once reduced to an array, the problem becomes same as point update and range query. We can flatten the tree by pushing nodes to the array in the order of visiting them during a DFS. This ensures the entire subtree of a particular node forms a contiguous subarray in the resultant flattened array. The range of indices corresponding to subtree of a node can also be pre-calculated using a timer in DFS.

Code

Path Queries

This problem can be solved using Heavy-Light decomposition of trees.

First, we decompose the tree into chains using heavy-light scheme and then build a segment tree over each chain. A path from node u to v can seen as concatenation of these chains and each query can be answered by querying the segment trees corresponding to each of these chains on the path. Since heavy-light scheme ensures there can be at most $$$O(logn)$$$ chains, each query can be answered in $$$O(log^{2}n)$$$ time.

Similarly, each update can be performed in $$$O(logn)$$$ time as it requires update on a single chain (single segment tree) corresponding to the given node.

Code

Distinct Colors

This problem can be solved using Mo's algorithm on trees and can be reduced to this classical SPOJ Problem

Flatten the tree to an array using the same technique mentioned in solution of Subtree Queries. Then the subtree of each node will correspond to a contiguous subarray of flattened array. We can then use Mo's algorithm to answer each query in $$$O(\sqrt{n})$$$ time with $$$O(n\sqrt{n})$$$ preprocessing.

Code
Alternate solution using small-to-large technique


End Notes

 
 
 
 
  • Vote: I like it
  • +84
  • Vote: I do not like it

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's been 4weeks and still, no one reacted?

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    This probably means he started working on the blog 4 weeks ago and not that he posted it 4 weeks ago.
    How long have you been using CF, smh xD

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Good job on the editorial!
you might like my DP solution(check code) for tree matching.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for mentioning! Seems like maximum matching was on overkill.

»
11 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Thanks for this editorial, might motivate many people like me to practice tree problems!

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please give the link for problemset.

»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Post is itself a good one, just a add on, read this awesome blog by adamant on heavy- light decomposition, using this we can solve both path queries as well as subtree queries simultaneously.

»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

There are some problems that can be done better :)

Tree Matching
Path Queries
Distinct Colors
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice observations!
    Will definitely try all these approaches.

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Tree Matching :Greedy — sort all the edges according to the number of subordinates then check and count whether the nodes in the edge is taken or not :)

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the full form of CSES?

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

You know many thing Jon.Snow.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the mention :)

»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for this! You can also add Graph editorials for CSES problem set to the list. They are not yet complete though

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

For Tree Distances I

max_distance[u] = max(distance_from_diametric_end1[u], distance_from_diametric_end2[u])

Is there any proof for this?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    First, suppose that $$$u$$$ is lying on diameter (path from $$$end1$$$ to $$$end2$$$). Now lets prove it by contradiction: suppose we can do (strictly) better. Without lose of generality, lets say that end1 is in the same "side" of the tree where is the node with whome we can do better (lets name that node $$$v$$$).

    So since $$$v$$$ is on the same side as end1, and you need to pass throw $$$u$$$ to get to that side from $$$end2$$$, then distance from $$$end2$$$ to $$$v$$$ can be shown as sum of distance (from $$$end2$$$ to $$$u$$$) + (from $$$u$$$ to $$$v$$$). And we assumed that distance from $$$u$$$ to $$$end1$$$¸is shorter then from $$$u$$$ to $$$v$$$. Then distance from end2 to $$$v$$$ is (strictly) greater than distance from end2 to end1. (but end1 to end2 is diameter — longest distance possible!)

    Simular can be shown if $$$u$$$ is not on diameter. Try working it out yourself! Good luck :)

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for the editorial bro.

»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice editorial man! Please keep adding stuffs like this. They are really helpful atleast for newbies and beginnners!

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Tree Diemeter, it can also be solved with 1 dfs instead of 2 dfs / 2 bfs.

code
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Distinct Colors be solved using Segment Tree? I tried but it gives TLE as merging two sets is taking linear time How do i optimise it?

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    Transform the problem into a range query problem on an array using dfs order (Let this array of colors be A)

    Let Prev[i] be the maximum index j<i such that A[j] = A[i] (-1 if no such j exists)

    Let's say we're counting the number of distinct values in the range [L, R].

    Fix a color and let's say its positions are p1, p2, ..., pk in increasing order. Observe that Prev[p1] < L and L <= Prev[pi] <= R for all 2 <= i <= k. Therefore, for each color C appearing at least once in the range [L, R], the number of indices i with C = A[i] and Prev[i] < L is exactly one.

    Sum it over all colors, and we obtain that (# of distinct colors in the [L, R]) = (# of indices with Prev[i] < L).

    Now our problem reduces to solving following range query problem: Given an array, process query of form "given a range [L, R] and a value X, find the number of values in [L, R] less than X".

    You can use one of followings to solve the above problem (I could be wrong on some complexities)

    (A) Wavelet Tree (O(N log MAXVAL) preprocessing, O(log N) per query, online)

    (B) Mergesort Tree (O(N log N) preprocessing, O(log^2 N) per query, online)

    (C) Any persistent data structure supporting point update and range query (O(N log N) preprocessing, O(log N) per query, online)

    (D) Any data structure supporting point update and range query(O(N log N) preprocessing, O(log N) per query, offline)

    I'll describe how to do (D). First three should easily be derivable once you know corresponding data structures. First, compress all the values if necessary.

    We prepare a data structure DS supporting point update and range addition query. Initially, it should be filled with 0.

    Solve the queries offline in increasing value of X.

    When we process the query [L, R] with X, we'll require DS to satisfy the following invariant: for each position 1<=i<=n, i-th value of DS is equal to one if and only if Prev[i] < X.

    Using this invariant, the answer to the current query is simply the range sum query [L, R] for DS.

    To preserve this invariant, we keep a sorted list of pairs (Prev[i], i), and then when we process the query, we pop the front of the list, update i-th position of our DS to one, as long as Prev[i] < X is satisfied.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In tree Distances (II) what does the sub[v] means ?