小H学历史
题号：NC281532
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小H今天在学校里学习了历史，小H对楚汉争霸的历史非常感兴趣，因此小H决定和同伴们玩一个两国争霸游戏。总共有 n 座城池，两座城池之间可能有道路相连。刚好有 n-1 条道路将所有城池连成了树的形状。每座城池一开始可以被 A,B 两个国家占领，或者是无主的城池 Z ，且一开始每个端点城池（只有一条道路和其他城池相连的城池）都不是无主的。每个国家可以占领与自己城池相连的城池，占领后可以进一步扩张势力，每个国家都希望占领尽可能多的城池，因此任何一座无主城池最终都会被占领。但是小H不希望游戏结束太快，因此希望两个国家势均力敌，小H想知道最终两个国家占领总城池数差最小值是多少？

输入描述:

第一行输入正整数 n, 表示有 n 座城池。
第二行输入 n 个字符 a_i, 表示第 i 座城池的所属国家。其中A,B 表示分别属于两个国家, Z 表示这个城池为无主的。
接下来 n-1 行，每行三个正整数 u,v, 表示 u 城池和 v 城池之间有一条道路。
1≤n≤10^5
1≤u,v≤n

输出描述:

一个非负整数，表示最少两个国家占领总城池数差最小值。若 |A|,|B|为最终两国家占领总城池数，请输出 \lVert|A|-|B|\rVert。
示例1

输入

复制 
5
A Z B A B
1 2
2 3
2 4
2 5

输出

复制 
1

说明

备注: