늑대인간

색이 칠해진 $n$개의 노드로 이루어진 트리가 주어진다. 노드 $i$의 색은 $c_i$이다. $n$개의 노드로 이루어진 트리는 $n-1$개의 간선으로 이루어진 연결 그래프이다.

이 트리의 연결된 부분그래프 중에서, 어떤 색 (다수색)이 부분그래프 노드의 절반을 엄격하게 초과하는 것의 개수를 구하라. 답이 클 수 있으므로 $998\,244\,353$으로 나눈 나머지를 출력한다.

첫 줄에 노드의 개수 $n$ ($1 \le n \le 3000$)이 주어진다. 둘째 줄에는 노드의 색 $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le n$)이 주어진다. 다음 $n-1$개 줄에는 트리의 간선 $u_i$와 $v_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$)가 하나씩 주어진다. 주어지는 그래프는 트리이다.

다수색을 가진 연결된 부분그래프의 개수를 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력한다.

그림에서 색 1은 파란색, 색 2는 빨간색, 색 3은 노란색으로 표시한다. 첫 번째 그림에서 1번과 2번 노드로 이루어진 부분그래프는 빨간색과 노란색이 각각 한 번씩 나오므로 다수색이 없다.