P10536 [Opoi 2024] Twenty-Six Points.
Background
Twenty-six points:
> 。 。 。 。 。 。 。 。 。 。 。 。 。
>
> 。 。 。 。 。 。 。 。 。 。 。 。 。
Making twenty-six points is really fun, and in order to make up four problems, this number-composition problem with only $26$ kinds of weights was created.
Description
You are given a rooted tree $T$ with $n$ nodes, rooted at $1$. The $i$-th node has a color $c_i$, where ${\tt a} \le c_i \le {\tt z}$, and a value $P_i$.
For each node $x$, there is a path **from it to every node in its subtree** (note that the order is from itself to a node in its subtree), for a total of $\text{size of subtree}$ paths.
Now, ignore the $2$-nd to the $P_x$-th nodes on each of these paths. In particular, if $P_x = 1$, then no nodes are ignored. Treat the path after ignoring as a sequence, where the weight of each node in the sequence is the $c_i$ of the node on the path. For **each node**, find the maximum, over all its sequences, of the length of the longest non-decreasing subsequence.
Note: If a path $j$ has $len_j < P_x$ nodes, this is equivalent to ignoring all nodes on this path except the first node.
Input Format
The first line contains an integer $n$.
The second line contains $n$ integers $P_i$.
The third line contains $n$ lowercase letters $c_i$, **with no spaces between characters**.
Next $n - 1$ lines describe the tree $T$. Each line contains two integers $u, v$, meaning there is an edge between $u$ and $v$.
There may be extra spaces at the end of lines (use `getchar()` with caution).
Output Format
Output $n$ lines, the answer for each node, in order of increasing index.
Explanation/Hint
### Explanation of Sample 1:
The shape of the tree in the sample:
For node $1$:
$P_1=2$.
| Sequence | Weights | Length of LNDS | LNDS |
| :----------: | :----------: | :----------: | :----------: |
| 1 | z | 1 | z |
| 1 3 | za | 1 | z |
| 1 3 4 | zab | 2 | ab |
| 1 3 5 | zac | 2 | ac |
| 1 3 5 6 | zaca | 2 | ac |
| 1 3 5 7 | zacd | 3 | acd |
The LNDS with the maximum length: acd.
Node $2$ is the same as node $1$.
For node $3$:
$P_3=1$.
| Sequence | Weights | Length of LNDS | LNDS |
| :----------: | :----------: | :----------: | :----------: |
| 3 | a | 1 | a |
| 3 4 | ab | 1 | ab |
| 3 5 | ac | 2 | ac |
| 3 5 6 | aca | 2 | ac |
| 3 5 7 | acd | 3 | acd |
The LNDS with the maximum length: acd.
For $4, 5, 6, 7$, each of their sequences contains only the node itself, so output $1$.
### Constraints
This problem uses Subtask scoring.
| Subtask | Limit | Pts |
| :-----------: | :-----------: | :-----------: |
| 0 | $n \le 100$ | 5 |
| 1 | $n \le 2000$ | 15 |
| 2 | $\forall 1 \le i \le n \quad P_i=1$ | 30 |
| 3 | Empty | 50 |
For $100\%$ of the testdata:
$1 \le n \le 10^5$.
$\forall 1 \le i \le n$, $c_i$ is a lowercase letter, and $1 \le P_i \le n$.
The given tree is connected and valid.
Translated by ChatGPT 5