5316: Cut the Tree
内存限制：512 MB
时间限制：4.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
Assume we walk along the shortest path from node u to node v in the weighted tree T. List the values of passing nodes (including u and v) on the sequence in order, and denote Fu,v(S) as the length of Longest Increasing Subsequence for that sequence. Further denote Fmax(S) as:
Fmax(S)=maxFu,v(S)(u,v∈S)
After removing node k in an unrooted tree S, we collect the remaining subtrees as a set and call it Sk.
Denote Gk(S) as:
Gk(S)=maxFmax(T)(T∈Sk)
Now you are given a weighted tree S with n nodes, you should determine a node k so that the value of Gk(S) is minimum. In other words, please calculate:
Gmin(S)=minGk(S)(k∈S)
Fmax(S)=maxFu,v(S)(u,v∈S)
After removing node k in an unrooted tree S, we collect the remaining subtrees as a set and call it Sk.
Denote Gk(S) as:
Gk(S)=maxFmax(T)(T∈Sk)
Now you are given a weighted tree S with n nodes, you should determine a node k so that the value of Gk(S) is minimum. In other words, please calculate:
Gmin(S)=minGk(S)(k∈S)
输入
The first line of input contains one integer n(2≤n≤105), indicating the number of nodes.
In the next n−1 lines, there are two integers (ui,vi)(1≤ui,vi≤n)in a line, describing the i-th edge on the tree.
There are n integers a1,…,an(1≤ai≤n) in the last line, ai indicates the value on the node i.
In the next n−1 lines, there are two integers (ui,vi)(1≤ui,vi≤n)in a line, describing the i-th edge on the tree.
There are n integers a1,…,an(1≤ai≤n) in the last line, ai indicates the value on the node i.
输出
Output one integer in a line, indicating Gmin(S).
样例输入 复制
6
1 2
2 3
3 4
4 5
5 6
1 2 3 4 5 6样例输出 复制
3