Maximizing Adjacent Service Clusters

You are given a cluster deployed on a tree‐network. The cluster has 2n machines (numbered from 1 to 2n) and n services (numbered from 1 to n). Each service runs exactly two replicas, and every machine runs exactly one replica. The network of machines is given as a tree with 2n-1 edges (direct connections) so that there is a unique path between any two machines.

You are also given a sequence a₁, a₂, \dots, a_2n, where a_i is the service running on machine i. Your extension can perform some swap operations in order to maximize the cluster performance. A swap operation picks two machines i and j and swaps the values a_i and a_j. Each machine is allowed to participate in at most one swap. (A machine that does not swap keeps its original service assignment.)

The cluster performance is measured as the number of services whose two replicas are placed on two machines that are directly connected by an edge in the tree. In other words, after the swaps, for a service s we want there to exist an edge \((u,v)\) in the tree such that the final labels at u and v are both \(s\). Note that if a service is already running on two adjacent machines then no swap is needed. Otherwise, the only way to fix a service is to choose one replica to remain (unswapped) and swap the other replica with some machine v that is adjacent to the unswapped replica so that after swapping the machine v gets service \(s\). However, since swaps are done only in pairs and each machine can be involved in at most one swap, you cannot arbitrarily relocate replicas.

Formally, let the initial configuration be \(a_1,a_2,\dots,a_{2n}\) and suppose service \(s\) initially appears at machines \(i\) and \(j\). We say service \(s\) is fixed if one of the following holds:

• \(i\) and \(j\) are adjacent in the tree (and no swap is needed), or
• You perform a swap between the replica from \(i\) (or \(j\)) and some machine \(v\) which is adjacent to the other replica so that after the swap the unswapped replica and machine \(v\) both hold service \(s\).

Your task is to choose a set of swap operations (each machine can be used at most once in a swap) so that the number of fixed services is maximized. Output the maximum number of services that can have their two replicas on two directly connected machines after the swaps.

Note: In a swap operation, if a machine participates then its final label becomes that from its swap partner. Therefore, if a service \(s\) is fixed via a swap then the two final copies of \(s\) must come from the two original copies for \(s\).

The key observation is that for services that are not initially fixed (i.e. their two replicas are not on adjacent machines), the only possible way to fix them is to transfer one copy via a swap from one of its original locations to a machine that is adjacent to the other copy. This yields a bipartite matching formulation between the set of unfixed services and candidate machines that can serve as swap partners. The answer is the sum of the number of services initially fixed and the maximum matching size.

Input Format:

n
u1 v1
u2 v2
...
u(2n-1) v(2n-1)
 a1 a2 ... a(2n)

Here, n is the number of services, the next 2n-1 lines each contain two integers denoting an edge between machines, and the last line contains 2n integers (each between 1 and n) representing the service deployed on each machine.

Output Format:

X

Output a single integer X, the maximum number of services that can have both their replicas on two directly connected machines after performing the allowed swaps.

Constraints: It is guaranteed that each service appears exactly twice and the given network forms a tree. All formulas should be interpreted in \(\LaTeX\) format.

inputFormat

The first line contains an integer \(n\) representing the number of services. There are \(2n\) machines.

The next \(2n-1\) lines each contain two integers \(u\) and \(v\) (\(1 \le u,v \le 2n\)) which denote a direct connection (edge) between machines \(u\) and \(v\). It is guaranteed that these edges form a tree.

The last line contains \(2n\) integers \(a_1,a_2,\dots,a_{2n}\) (each between \(1\) and \(n\)), where \(a_i\) is the service number running on machine \(i\). Each service appears exactly twice.

outputFormat

Output a single integer representing the maximum number of services that can be fixed, i.e. the number of services for which the two replicas end up on adjacent machines after performing the allowed swaps.

sample

2
1 2
2 3
3 4
1 2 1 2

2