#P18921. [2026多校联测]树莓根下

[2026多校联测]树莓根下

树莓根下(respberry)

题目背景

题目背景

题目描述

树莓的根可以抽象成一棵包含 nn 个节点的树,根节点为 11,每条边上有一个从 aa 到 vv 共 2222 个小写英文字母之一,每个节点有一个权值 ri<3r_i < 3。

对于一个节点 uu,我们称一个点对 (x,y)(x,y) 是好的满足以下条件:

  • x,yx,y 在 uu 的子树(不用不同)。

  • 路径上的英文字母可以重排后组成一个回文串。

  • dis(x,y)≡rumod  3\text{dis}(x,y) \equiv r_u \mod 3

    请你求出对于每个 uu 而言,好的点对的最长路径长度。

输入格式

输入的第一行包含一个非负整数 nn,含义如上。

接下来第二行包含 nn 个非负整数 rir_i,含义如上。

接下来 n−1n-1 行描述这棵树。

对于 i=2,3,…,ni=2,3,\ldots,n,依次读入一个整数和一个字符 pi,cip_i,c_i,表示 ii 的父亲为 pip_i,边上的字符为 cic_i。

输出格式

输出 nn 个数,表示答案,没有路径时输出 −1-1。

输入输出样例

样例一

输入
7
0 1 2 0 1 2 1
1 a
1 b
2 b
2 a
3 a
3 b
输出
3 1 -1 0 -1 -1 -1
解释

对于节点 11,可以选择 (2,6)(2,6)。

对于节点 44,可以选择 (4,4)(4,4)。

数据范围

本题采用子任务捆绑,只有通过子任务中的全部测试点才可获得分数。

本题有极大的子任务依赖。

子任务编号 nn 特殊性质 分数
11 10210^2 无 1010
22 3×1033 \times 10^3 2525
33 5×1055 \times 10^5 pi=i−1p_i = i-1
44 pi=1p_i = 1 1010
55 无 3030