#P5365. [Lydsy1805月赛]回文树

    ID: 4378 传统题 4000ms 1024MiB 尝试: 224 已通过: 49 难度: 6 上传者: 标签>难度分类提高枚举与搜索暴力枚举树算法LCA树上倍增概率与期望期望线性性CF1900

[Lydsy1805月赛]回文树

回文树

题目描述

给定一棵 nn 个点的树,节点编号为 1∼n1\sim n。节点 ii 上有正整数 aia_i。

令 S(u,v)S(u,v) 为从 uu 到 vv 的唯一路径上,按从 uu 到 vv 的顺序读到的整数序列。如果这一序列正着读和倒着读相同,则称它为回文。例如 1 2 1 和 1 3 3 1 是回文,而 1 21 不是。每个节点上的整数是序列的一个元素。

求满足 1≤u≤v≤n1\le u\le v\le n 且 S(u,v)S(u,v) 是回文的点对 (u,v)(u,v) 数量。

输入格式

从标准输入读入。第一行一个正整数 TT(1≤T≤201\le T\le20),表示数据组数。

每组数据第一行一个正整数 nn(1≤n≤1000001\le n\le100000)。第二行 nn 个正整数 a1,a2,…,ana_1,a_2,\ldots,a_n(1≤ai≤n1\le a_i\le n);原题说明每个 aia_i 可视为在 [1,n][1,n] 内等概率随机选取。

接下来 n−1n-1 行,每行两个不同的节点编号 ui,viu_i,v_i(1≤ui,vi≤n1\le u_i,v_i\le n),表示一条无向树边。

输出格式

向标准输出对每组数据写出一行一个整数,表示满足条件的点对数。

样例

输入

2
3
1 2 1
1 2
2 3
2
2 2
1 2

输出

4
3