#P18404. Palindromic Beads
Palindromic Beads
Palindromic Beads
你准备探索一个遍布美丽珠子的洞穴。洞穴有 个房间,编号为 ;这些房间由 条双向隧道连接,构成一棵树。第 个房间恰有一颗颜色为 的珠子。
由于洞穴不属于你,你的行动受到限制。进入洞穴前,你必须选择两个房间 (可以有 ),并向洞穴主人申请。随后,你只能从房间 进入,沿着 到 的最短路径行走。
每当你到达一个房间时,包括起点 和终点 ,都可以选择取走或不取走该房间的珠子。最后,你把取走的珠子按照取得的先后顺序串成一串。珠子的颜色序列必须构成回文,否则你不能把这些珠子带回家。一个序列是回文,当且仅当从左向右读与从右向左读得到的序列相同。
你希望得到的回文串尽可能长。请问你最多可以带走多少颗珠子?
输入格式
第一行包含一个整数 (),表示房间数。
第二行包含 个整数 (),表示各房间珠子的颜色。保证每种颜色至多出现两次。
接下来 行,每行包含两个整数 (,),表示一条连接这两个房间的双向隧道。保证所有隧道构成一棵树。
输入只有一组数据。
输出格式
输出一行一个整数,表示最多可以带走的珠子数。
样例 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