Sweeping Robot on a Unicyclic Graph

You are given a connected undirected graph with n vertices and n edges. The graph has no self‐loops and no multiple edges; hence it contains exactly one cycle (i.e. it is unicyclic).

Each vertex i has an associated label \(t_i\) where \(t_i \in \{0,1\}\). A sweeping robot starts at an arbitrary vertex. When it visits a vertex i, if \(t_i=1\) the robot cleans that vertex (each vertex is cleaned at most once even if visited more than once). The robot is allowed to traverse edges without repetition (i.e. each edge may be used at most once), and the path does not need to be simple in terms of vertices (but cleaning is done only the first time a vertex with \(t_i=1\) is encountered).

Your task is to select a starting vertex and a route satisfying the edge constraint such that the number of cleaned vertices (i.e. vertices with \(t_i=1\) that are visited) is maximized. In other words, you need to find the maximum number of vertices with \(t_i = 1\) that can appear on a single trail (a walk that does not repeat edges) in the graph.

Input Format (also see Input section below):

• The first line contains an integer n denoting the number of vertices (and also the number of edges).
• The second line contains n space‐separated integers \(t_1, t_2, \dots, t_n\), each equal to 0 or 1.
• Then follow n lines, each containing two integers u and v denoting an undirected edge between vertices u and v (vertices are numbered from 1 to n).

Output Format (also see Output section below):

• A single integer: the maximum number of vertices with \(t_i=1\) that can be cleaned following a route that uses each edge at most once.

Problem Details and Hints:

• The graph is unicyclic, so it is essentially a tree with one extra edge. In a tree (or a tree branch attached to the cycle), if you attempt to visit two different branches you might have to re‐use an edge. Hence, any valid route in a tree is a simple path.
• The optimal route may lie entirely in one of the tree branches or may go through several vertices on the unique cycle while possibly attaching to extra branches. For a cycle segment (i.e. a contiguous segment of the cycle in its cyclic order) you may use extra tree paths at its two endpoints. More precisely, if you list the cycle vertices as \(v_1,v_2,\dots,v_k\) (in order along the cycle) and define \(w(v)=t_v\) for the base weight and an extra extension value from the tree attached at \(v\), then for a segment from \(v_i\) to \(v_j\) you may achieve a total of \[ \left(\sum_{p=i}^{j} w(v_p)\right) + \text{ext}(v_i) + \text{ext}(v_j), \] where \(\text{ext}(v)\) is the maximum chain sum in the tree attached to \(v\) (computed via DFS). You also need to consider the best simple path lying completely in one of these tree branches (its diameter). The answer is the maximum over these possibilities.

Note on formulas: All formulas are given in \(\LaTeX\) format.

inputFormat

The input begins with a single integer n (n vertices and n edges). The second line contains n space-separated integers \(t_1, t_2, \dots, t_n\) where each \(t_i\) is either 0 or 1. This is followed by n lines; each line contains two integers u and v (1-indexed) representing an edge between vertices u and v.

outputFormat

Output a single integer representing the maximum number of vertices that can be cleaned by the robot following a path where each edge is used at most once.

sample

3
1 0 1
1 2
2 3
3 1

2