Background

In-contest Q&A

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.

Problem Description

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.

Input Format

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 Format

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

3 1
1
2 1
3 2

1

7 3
LDLD
tk_sky LDLD
Jayden_deng LDLD
only_xiaohuang tk_sky
Muddled_xiaopan tk_sky
Inkn only_xiaohuang
ipdjkl only_xiaohuang

8

Hint

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