Palindromic Beads
Description
You are going to explore a cave full of beautiful beads. The cave consists of $n$ rooms labeled by $1,2,\dots,n$, connected by $(n-1)$ bidirectional tunnels like a tree. In the $i$-th room, there is exactly one bead colored $c_i$.
The cave is not owned by you, so your actions are restricted. Before your entrance to the cave, you need to select two rooms $x$ and $y$ (maybe $x=y$), and submit your application to the owner. Then you can enter the cave at the $x$-th room, and walk along the shortest path from the $x$-th room to the $y$-th room. Every time you visit a new room, including the first room $x$ and the last room $y$, you can choose to either pick the bead in that room up or not. Finally, you need to concatenate all the beads that you picked up into a string according to the order you picked them up. You must ensure the colors of each bead in the string is palindromic, otherwise you are not allowed to take these beads back home. Note that a string is palindromic if and only if it reads the same from left to right and vice versa.
You want to make the palindromic string as long as possible. What's the maximum possible number of beads that you can take away?
The first line of the input contains a single integer $n$ ($1 \leq n \leq 200\,000$), denoting the number of rooms.
The second line contains $n$ integers $c_1,c_2,\dots,c_n$ ($1\leq c_i\leq n$), denoting the color of the bead in each room. It is guaranteed that each color will appear at most twice.
Each of the next $(n-1)$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$), denoting a bidirectional tunnel between the $u_i$-th room and the $v_i$-th room. It is guaranteed that the roads form a tree.
Print a single line containing an integer, denoting the number of beads that you can take away.
Input
The first line of the input contains a single integer $n$ ($1 \leq n \leq 200\,000$), denoting the number of rooms.
The second line contains $n$ integers $c_1,c_2,\dots,c_n$ ($1\leq c_i\leq n$), denoting the color of the bead in each room. It is guaranteed that each color will appear at most twice.
Each of the next $(n-1)$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i \neq v_i$), denoting a bidirectional tunnel between the $u_i$-th room and the $v_i$-th room. It is guaranteed that the roads form a tree.
Output
Print a single line containing an integer, denoting the number of beads that you can take away.
4
1 1 2 2
1 2
2 3
2 4
5
1 3 2 2 1
1 2
2 3
3 4
4 5
3
4