Hello everyone!

In this blog, I will describe an (O(n)) construction for E. Building a Tree.

The main ideas are:

• checking the valid range of (k);
• rooting the tree at vertex (1);
• separating even and odd vertices into two branches;
• reducing the required distance sum to a depth sum;
• greedily assigning depths.

Hello everyone!

In this blog, I will describe a solution for E1. String (Easy Version).

The main ideas are:

• split the infinite sequence into blocks whose length is a power of (k);
• remove the block-dependent shift using adjacent differences;
• use the Z-function to compare the pattern with all offsets;
• use digit DP to count suitable block indices.