#P18404. Palindromic Beads

Palindromic Beads

Palindromic Beads

你准备探索一个遍布美丽珠子的洞穴。洞穴有 nn 个房间,编号为 1,2,…,n1,2,\ldots,n;这些房间由 n−1n-1 条双向隧道连接,构成一棵树。第 ii 个房间恰有一颗颜色为 cic_i 的珠子。

由于洞穴不属于你,你的行动受到限制。进入洞穴前,你必须选择两个房间 x,yx,y(可以有 x=yx=y),并向洞穴主人申请。随后,你只能从房间 xx 进入,沿着 xx 到 yy 的最短路径行走。

每当你到达一个房间时,包括起点 xx 和终点 yy,都可以选择取走或不取走该房间的珠子。最后,你把取走的珠子按照取得的先后顺序串成一串。珠子的颜色序列必须构成回文,否则你不能把这些珠子带回家。一个序列是回文,当且仅当从左向右读与从右向左读得到的序列相同。

你希望得到的回文串尽可能长。请问你最多可以带走多少颗珠子?

输入格式

第一行包含一个整数 nn(1≤n≤200 0001\le n\le200\,000),表示房间数。

第二行包含 nn 个整数 c1,c2,…,cnc_1,c_2,\ldots,c_n(1≤ci≤n1\le c_i\le n),表示各房间珠子的颜色。保证每种颜色至多出现两次。

接下来 n−1n-1 行,每行包含两个整数 ui,viu_i,v_i(1≤ui,vi≤n1\le u_i,v_i\le n,ui≠viu_i\ne v_i),表示一条连接这两个房间的双向隧道。保证所有隧道构成一棵树。

输入只有一组数据。

输出格式

输出一行一个整数,表示最多可以带走的珠子数。

样例 1

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

样例 2

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