Longest Path with Ones in a Tree

You are given an undirected tree with n nodes where each node has a binary value (either 0 or 1). Your task is to compute the length of the longest simple path such that both its endpoints have a value of 1. A simple path is a path without repeated nodes.

If the tree does not have at least two nodes with value 1, output 0.

The tree is given in an edge list format. The nodes are numbered from 1 to \(n\). The length of a path is defined as the number of edges in that path.

inputFormat

The input is read from stdin and has the following format:

n
v1 v2 ... vn
u1 v1
u2 v2
... (n-1 lines)

Here, n is the number of nodes, followed by a line containing n integers representing the values of the nodes (either 0 or 1). Each of the following n-1 lines contains two integers representing an edge between two nodes.

outputFormat

Output a single integer to stdout which is the length of the longest path connecting two nodes with value 1. If no such path exists, output 0.

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

3