Editorial : Closer

There are $2n$ people standing on the $2n$ vertices of a tree. Each person wears a badge; each deal id $1, 2, \ldots, n$ appears on exactly two badges. A deal $i$ pays $w_i$ if, after your moves, the two people who care about deal $i$ stand on adjacent vertices.

You may perform one reshuffle: pick a set of edges that pairwise do not touch (a matching), and along every chosen edge swap the two people there. You want maximum total profit.

Think of it as a routing puzzle: you are allowed to teleport people along a few disjoint edges, once. The tree geometry matters because “adjacent” means tree-adjacent.

Warm-up A ($n = 1$). Two vertices, one edge. Either you use that edge in the matching or you do not. If you use it, the two people swap; if not, nothing moves. In either case the two copies of the only badge stay on the endpoints of the same edge, so the deal is always sealed. Profits only become subtle when many deals share the same tree.

Warm-up B (read the first sample mentally). On a path of four vertices, badges might be placed so that each label is not yet on an edge with its partner. Swapping outer pairs can rotate people so that a label’s two copies meet on a middle edge. So the reshuffle really changes who is next to whom.

Matching constraint. Each vertex has one body. If a vertex participated in two different swaps, it would need to exchange identities with two neighbors at the same time, which is impossible. So valid reshuffles are exactly matchings in the tree.

Root the tree at an arbitrary vertex $r$. Focus on a vertex $v$ with parent $p$ (if $v \neq r$). Along the edge $p\text{--}v$, either:

1. nothing uses that edge for a swap, or
2. exactly one swap uses it, namely $p$ and $v$ trade places.

Moreover, if $v$ also swaps with one of its children, then $v$ would be in two swaps. Therefore, for every vertex $v$ the possibilities are:

• stay: $v$ does not swap with its parent;
• swap-up: $v$ swaps with its parent;
• swap-down: $v$ swaps with one chosen child (and not two).

The root has no parent, so its options are only stay or swap-down with one child.

This turns the problem into a tree DP: children must send enough information upward so that their parent can decide whether to use the parent edge, and if so, how edge profits along other links should be counted.

Fix the initial badge array $a[\cdot]$. For an undirected edge $\{x, y\}$, after all swaps are done, let $b[x]$ and $b[y]$ be the badges at its endpoints. That edge contributes

because only then are the two vertices hosting the same deal id and they are adjacent.

Important subtlety. Even if $a[x] = a[y]$ before swaps, the people might move; you only care about final badges. Conversely, a label’s two copies might start far apart and become adjacent only after swaps.

Ignore, for a moment, the fact that each badge appears twice in the whole tree. For a child $u$ of $v$, if the edge $v\text{--}u$ is not used for a swap, then the people at $v$ and $u$ are still the original ones, so the edge contributes $w_{a[v]}$ iff $a[u] = a[v]$.

If $u$ might swap with one of its own children, then the badge at $u$ after processing its subtree is not determined by $a[u]$ alone. A convenient bookkeeping device is:

• For each vertex $u$, store a small list of possibilities of the form $(\text{badge at } u,\ \text{best profit in } u\text{'s subtree})$ when $u$ is in “I do not swap with my parent” mode, and similarly when $u$ does swap with its parent.

In code, those lists are trimmed and sorted so you can merge and query them quickly.

At a vertex $v$, to compute the “stay” option, you sum over children $u$ the best value compatible with the edge $v\text{--}u$, including the possible $w$ bonus if the final badges on $v$ and $u$ match.

Here is the conceptual heart of the problem. Suppose you decide that $v$ swaps with a child $u$. After that swap, the person standing at $v$ is the one who used to stand at $u$, so $v$ displays badge $a[u]$ (the old badge at $u$).

Now look at the other vertex $w$ with the same badge as $u$: by definition $a[w] = a[u]$ and $w \neq u$. Call this $w = \mathrm{partner}(u)$.

• If $w$ is another child of $v$, then after the swap $v\text{--}u$, the edge $v\text{--}w$ connects two vertices that both show badge $a[u]$. That seals deal $a[u]$ using an edge incident to $v$ in a way that your earlier “sum of child defaults” might not have priced in optimally for $w$’s subtree.

  Intuitively, you counted $w$’s subtree using whatever was locally optimal before you knew that $v$ would suddenly display $a[u]$. If making $v\text{--}w$ valuable requires a different internal arrangement inside $w$’s subtree, you should add the profit increase from switching to that arrangement.

• If $w$ is not adjacent to $v$, but sits two steps away as $v\text{--}m\text{--}w$ with $m \neq u$, then the relevant incident edge to $v$ for that duplicate pair is $v\text{--}m$, not $v\text{--}w$. After $v$ swaps with $u$, the badge at $v$ becomes $a[u]$, so the profit on $v\text{--}m$ depends on what badge ends up at $m$. That is exactly what the “list of (badge at $m$, best profit)” is for: you may need to pick the entry whose badge matches what $v\text{--}m$ wants under the new boundary condition.

These two geometric cases are the only partner locations that share an edge with $v$ besides $u$ itself: either $w$ is a sibling of $u$, or $w$ hangs off a sibling $m$ of $u$.

For each vertex $v$ in post-order:

1. Stay at $v$ (no swap with parent): sum over children the best “child does not swap with $v$ on that edge” values, including edge bonuses between $v$ and each child given that $v$ still shows $a[v]$.

2. Swap $v$ with its parent: analogous aggregation, except every edge $v\text{--}u$ must be evaluated as if $v$ displays $a[p]$ (the parent’s old badge), because that is who moved down to $v$.

3. Swap $v$ with a specific child $u$: start from the sum of children’s default internal bests (ignoring the $v\text{--}u$ hook-up for a moment), then replace $u$’s contribution by the “$u$ swaps with its parent $v$” variant instead of $u$’s default. Finally, add the partner-based corrections from Level 4: for $w = \mathrm{partner}(u)$, add the nonnegative gain from adjusting the relevant subtree (sibling case or the $v\text{--}m$ case).

The answer at the root is the maximum over “root stays” and “root swaps with some child” (there is no parent swap).

Each vertex has a list of length at most its degree; sorting these lists yields $O(n \log n)$ time and $O(n)$ memory, which fits $n \le 10^5$.

The tree is a path on six vertices with badges $1,2,3,1,2,3$ along the line. Choosing the matching of the three disjoint edges $(1,2)$, $(3,4)$, $(5,6)$ rotates people so that the middle edges $(2,3)$ and $(4,5)$ become monochromatic for deals $1$ and $3$, paying $w_1 + w_3$. The DP’s purpose is to automate this kind of global reasoning on an arbitrary tree.

• The matching constraint localizes to at most one incident swap per vertex.
• A clean tree DP tracks, for each edge to a parent, whether it is used.
• Because each badge appears twice, changing who sits at $v$ can change more than one nearby edge profit; the partner of the child you swapped with supplies the missing correction, in one of two simple shapes (sibling or nephew subtree).

That is the whole idea: local swap choices, plus one nonlocal bookkeeping fix coming from the unique duplicate of a badge near the top of a subtree.