SP23821 HCMUS20A - Magic Schools

你是小镇上最聪明的小兵，为弟弟斯图尔特挑选下学年入读的魔法学校。在梦幻想象镇（FIT），共有 $N$ 所魔法学校，分别教授蓝色魔法或白色魔法。学校之间由 $N-1$ 条双向道路连接，每条道路连接两所不同的学校。所有学校的连接使得任意两所学校之间都存在一条唯一的路径。 你计划拜访一些学校，每所学校都有一个幸福值，访问该学校时你的幸福感会相应增加或减少（如果该值为负数）。 为了安排这次拜访，你需要选择两所不同的学校，作为行程的出发点和目的地。在两者之间的路径上，你会访问所有的学校，包括这两所。为了平衡，你必须确保蓝色魔法学校和白色魔法学校的数量相等。 你想知道怎样的行程能使幸福感达到最大，也就是路径上所有学校幸福值之和最大。 根据给定的学校信息和它们之间的连接，找出一个最优行程，使得访问的蓝色魔法学校和白色魔法学校数量相等，并且幸福感最大。

输入包括四行： 第一行：一个整数 $N$（$2 \le N \le 10^5$），表示学校的总数（学校编号从 $1$ 到 $N$）。 第二行：一个由 "B" 和 "W" 组成的长度为 $N$ 的字符串。如果第 $i$ 个字符是 "B"，则第 $i$ 所学校教授蓝色魔法；如果是 "W"，则第 $i$ 所学校教授白色魔法。至少存在一所教授白色魔法的学校和一所教授蓝色魔法的学校。 第三行：$N$ 个用空格分隔的整数 $h_1, h_2, \ldots, h_N$（$-10^5 \le h_i \le 10^5$），表示第 $i$ 所学校的幸福值。 第四行：$N-1$ 个用空格分隔的整数 $v_1, v_2, \ldots, v_{N-1}$。整数 $v_i$ 表示存在一条道路连接编号为 $v_i$ 和 $i+1$ 的学校（$1 \le v_i \le i$）。

输出一个整数，表示满足访问相同数目蓝色和白色魔法学校的最优路径中，最大得到的总幸福值。 **本翻译由 AI 自动生成**