问题描述
Alex有一棵$n$个节点的树$T$, 节点标号依次为$1,2,...,n$. 每个节点都被染色成白色或者黑色. 对于每对整除$(a, b)$, Alex想要知道是否存在一个$T$的联通子树使得恰好有$a$个白色节点, 恰好有$b$个黑色节点.
输入描述
输入包含多组数据, 第一行包含一个整数$T$ $(1 \le T \le 100)$表示测试数据组数. 对于每组数据:
第一行包含一个整数$n$ $(1 \le n \le 2000)$. 接下来包含一个长度为$n$的二进制串$s$, $s_i$表示第$i$个节点的颜色 ('0'表示白色, '1'表示黑色). 接下来$n - 1$行每行包含两个整数$a_i, b_i$, 表示节点$a_i$和$b_i$之间有一条边 $(1 \le a_i, b_i \le n)$.
输出描述
对于每组数据, 输出一个整数$W = \sum_{a=0}^{n}\sum_{b=0}^{n}{(a+1)(b+1)S(a,b)}$. 如果存在一个子树, 使得恰好有$a$个白色节点, 恰好有$b$个黑色节点, 那么$S(a,b)=1$, 否则$S(a,b)=0$.
输入样例
3
4
1010
1 4
2 4
3 4
3
101
1 2
2 3
10
1010111001
1 2
1 3
1 8
2 4
2 6
2 7
3 9
4 5
7 10
输出样例
33
15
365
