Longest Alternating Path in a Tree

Given a tree with n nodes, where each node has an associated integer value, find the length of the longest path in the tree such that the parity of consecutive nodes alternates between even and odd. Formally, if the values along the path are \(a_1, a_2, \dots, a_k\), then for every adjacent pair \(a_i\) and \(a_{i+1}\) (with \(1 \leq i < k\)), it must hold that \(a_i \not\equiv a_{i+1} \pmod{2}\).

The tree is given as an undirected graph with n nodes and exactly n-1 edges. It is guaranteed that the input forms a valid tree.

inputFormat

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

The first line contains an integer n, the number of nodes in the tree.
The next n-1 lines each contain two integers u and v indicating an edge between nodes u and v.
The last line contains n integers representing the values at the nodes (the i-th integer is the value at node i).

outputFormat

Output a single integer on standard output, which is the length of the longest path with alternating even and odd values.

5
1 2
1 3
3 4
3 5
4 2 7 6 5

3