Maximizing the Minimum Symmetric Difference between Maximum Weighted Independent Sets on Trees

Given a tree \(T=(V,E)\) with \(n\) vertices numbered \(1,2,\dots,n\) and an integer weight \(v(i)\) on each vertex \(i\), you are allowed to change the weight of exactly one vertex \(u\) to any integer value; all other vertex weights remain unchanged. Let the original weight function be \(v\) and the modified weight function be \(v'\) (with \(v'(i)=v(i)\) for all \(i\neq u\)).

For any weight function \(w\) on \(T\), define an independent set \(S\subseteq V\) (i.e. no two vertices in \(S\) share an edge) and its weight as \[ \mathfrak{v}_w(S)=\sum_{i\in S}w(i). \] Let the maximum weight of an independent set under \(w\) be \[ \mathfrak{V}_w(T)=\max\{\mathfrak{v}_w(S): S \subseteq V \text{ is an independent set}\}, \] and let the family of all maximum weighted independent sets be \[ \mathfrak{S}_w(T)=\{S \subseteq V : \mathfrak{v}_w(S)=\mathfrak{V}_w(T)\}. \]

Define the symmetric difference between two sets \(S\) and \(S'\) as \(S\Delta S'=(S\setminus S')\cup (S'\setminus S)\), and set \[ f_T(v,v')=\min_{S\in\mathfrak{S}_v(T),\,S'\in\mathfrak{S}_{v'}(T)} |S\Delta S'| . \] Your task is to choose a vertex \(u\) and a new weight for it (i.e. choose \(v'\)) so as to maximize \[ \max_{v'} f_T(v,v'). \] Output the maximum possible value.

Note: In this problem you only need to output the maximum value, not the actual modification.

inputFormat

The input consists of the following:

• The first line contains an integer \(n\) (the number of vertices).
• The second line contains \(n\) integers: \(v(1), v(2), \dots, v(n)\), the weights of the vertices.
• Each of the next \(n-1\) lines contains two integers \(u\) and \(w\) indicating an undirected edge between vertices \(u\) and \(w\).

outputFormat

Output a single integer representing the maximum possible value of \(\max_{v'} f_T(v,v')\).

sample

1
5

1