## LCC '21 Contest 6 S2 - Palindromes on Trees

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

Given a tree with one-way paths rooted at node composed of nodes each with a digit assigned to it, can a path along the tree be selected such that it starts at node and the digits on the path can be rearranged to form a number that reads the same forwards and backwards? A path should contain at least node.

#### Input Specification

The first line will contain a single integer , the number of nodes in the tree.

The line will contain space-separated digits, , , , , the -th digit being the digit on node .

The next lines will contain two integers each, and , representing a one-way path from to .

#### Output Specification

Output a single integer, the number of ways a unique path along the tree can be selected such that the digits can be rearranged to form a number that reads the same fowards and backwards.

#### Sample Input 1

5
1 2 1 2 1
1 2
2 3
3 4
4 5

#### Sample Output 1

4

#### Sample Input 2

3
1 1 2
1 2
1 3

#### Sample Output 2

2