P5034 Jelly

[In-contest Q&A](https://www.luogu.org/discuss/show/80694) **The testdata has been fixed**. [Survival World] Steve: Is there any dalao who can take me in qwq…… On a very friendly and harmonious Minecraft server, Steve loves to wander around. The server uses a town system, so there are many towns. One town is called Jelly Town. The mayor ~~looks very similar~~ likes eating jelly, and he loves ~~staring at the mirror~~ eating bling bling jelly. Suddenly, he received “good news” that the town would soon start a rebellion. He was shocked, quickly jumped out of bed (qwq), took a bite of jelly (oops), and started dealing with it.

There is one mayor in the town and $n-1$ townspeople. Each townsperson has their direct boss $f_i$. Each townsperson has a distance $d_i$ to the mayor (i.e., the number of bosses between them and the mayor plus $1$). The mayor wants every townsperson to become his direct subordinate, i.e., have distance $1$ from him. Each minute, he can make one townsperson become his direct subordinate. At minute $t (t > 0)$ (i.e., each minute, and $t$ starts from $1$), when this townsperson becomes his direct subordinate, the mayor gains a safety index of $(d_i+t) \& k$ (where $\&$ is the bitwise AND operator). Then **all subordinates of this townsperson will move together with this townsperson** (that is, this townsperson’s direct subordinates are still their subordinates, unless the mayor makes one of those subordinates his direct subordinate). After all townspeople become his direct subordinates, the mayor can eat his jelly in peace. Now he wants to ask you: how should he perform the changes to maximize the safety index? Since the mayor wants to eat jelly as soon as possible, he gives this task to you.

The first line contains two positive integers $n$ and $k$ (see the description for details). Starting from the second line, there are $n$ lines. Each line contains two strings (consisting of uppercase letters, lowercase letters, underscores, digits, apostrophes, or commas), representing a townsperson and their direct boss. **In particular, the second line is the mayor. He has no direct boss, so the second line contains only one string, representing the mayor**. The data guarantees that the second string has appeared before the first string.

Output one integer in a single line, representing the maximum safety value.

### Sample Explanation The second sample: (the images may fail to load, please wait a moment qwq)     Because ~~the problem setter is too lazy~~, the cases of moving child nodes are not listed. Please hack yourself. (troll) ### Constraints Note the following two special cases: 1. It is guaranteed that the string length is $1$. 2. The tree degenerates into a chain.  For all data, $k$ is guaranteed to be within the `int` range, and the string length does not exceed $10^6$. Both $n$ and $k$ are positive integers. Translated by ChatGPT 5