Hints: Closer
Answer to Hint 1: The two copies of a label need not start adjacent. Swaps move people along edges, so you can re-route who sits where. The path example works because after swapping the outer pairs, the two $1$s become neighbors on the middle edge.
Restate the allowed operation in graph language: you pick a set of edges that is a matching (no shared endpoints) and swap the two people on each chosen edge. Why is “no shared endpoint” the right formalization of “each person participates in at most one swap”?
Answer to Hint 2: A person is an endpoint of every swap they participate in. If a vertex touched two chosen edges, it would have to swap with two different neighbors at once, which is impossible. So the chosen swaps form a matching.
Warm-up ($n = 1$): two vertices, one edge. What is always true after any allowed reshuffle?
Answer to Hint 3: There is only one edge, so the matching can either be empty or use that edge. If it uses it, the two people swap; if not, nothing moves. In both cases the two badges are on the endpoints of the same edge, so the unique deal is always sealed. The interesting part of the problem is when several deals interact through the tree structure.
Root the tree arbitrarily at a vertex $r$. For a vertex $v \neq r$, its parent edge is the edge to its parent. Why can $v$ be involved in at most one swap among (parent edge) or (one child edge)?
Answer to Hint 4: Each swap uses two endpoints. If $v$ swapped with its parent and with a child, $v$ would be in two swaps. So at each vertex the local possibilities are: no swap, swap with parent, or swap with exactly one child (and not both).
This suggests a tree DP where each node passes “boundary information” to its parent about what happened on the parent edge. What quantity should the DP maximize on a rooted subtree before you worry about weights?
Answer to Hint 5: You want the maximum total profit from deals whose two endpoints are adjacent after all swaps. For the DP, first think about counting or detecting feasibility of a matching with swaps; then attach $w_i$ as additive rewards whenever a deal becomes adjacent.
Fix a rooted tree. For a child $u$ of $v$, consider the edge $v\text{--}u$. If no swap uses $v\text{--}u$, then the person standing at $u$ is still the original one. If a swap does use $v\text{--}u$, then the people at $v$ and $u$ trade places. How does this relate to “states” you need at $v$?
Answer to Hint 6: It is natural to keep, for each vertex $v$, a few cases: (A) $v$ does not swap with its parent; (B) $v$ does swap with its parent; (C) $v$ swaps with one particular child (you may need one option per child). Case (B) matters only when combining upward; the root has no parent, so its answer comes from (A) or (C).
For a fixed vertex $v$, let $a[x]$ be the badge at vertex $x$ before any swaps. If $v$ does not swap with its parent, when does the edge $v\text{--}u$ (child $u$) immediately contribute profit $w_{a[v]}$ from the pair whose badge equals $a[v]$?
Answer to Hint 7: After everything inside the subtrees is decided, the endpoints of $v\text{--}u$ are the people currently at $v$ and $u$. If neither side used a swap on that edge, they are the original badges $a[v]$ and $a[u]$. The edge contributes $w_{a[v]}$ only if $a[u] = a[v]$ (both endpoints show the same badge, which must be the unique deal id on that badge).
If instead $u$ swaps with one of its children, the badge at $u$ might change. What does your DP need to remember about $u$ beyond a single scalar “best value”?
Answer to Hint 8: When $u$ can swap with a child, the badge at $u$ after processing its subtree is not fixed in advance. It is useful to store, for each possible resulting badge at $u$, the best achievable profit in $u$’s subtree under the appropriate swap pattern. In implementation, you can compress this to a short list of pairs (badge at $u$, best profit).
Now aggregate children of $v$. Let $S$ be the sum, over children $x$, of each child’s “best internal profit” not counting the $v\text{--}x$ connection yet. If you decide that $v$ swaps with a specific child $u$, which child’s contribution should switch from the “default internal best” to the “swap-with-parent” variant?
Answer to Hint 9: Exactly the chosen child $u$: that edge is used for the swap between $v$ and $u$, so $u$ must be in the “swap with parent $v$” mode for its subtree math. All other children stay in the “no swap with $v$ on that edge” mode, still with their own internal options.
A first cut at the value of swapping $v$ with $u$ is therefore “replace $u$’s default piece by $u$’s parent-swap piece” inside the sum over children. Why is this still not always enough for optimality?
Answer to Hint 10: Changing who sits at $v$ can change more than one incident edge profit, because each badge appears twice in the whole tree. Swapping $v$ with $u$ moves the person who was at $u$ up to $v$. The other vertex with the same badge as that person might be near $v$ in a way that was not optimal under the old “$v$ keeps its original badge” accounting.
Let $w = \mathrm{partner}(u)$ be the unique other vertex with $a[w] = a[u]$. After swapping $v$ with $u$, vertex $v$ displays badge $a[u]$. If $w$ is a different child of $v$, what tree edge might newly seal the deal $a[u]$?
Answer to Hint 11: Look at the edge $v\text{--}w$. Before the swap, $v$ had badge $a[v]$; after swapping $v$ with $u$, vertex $v$ has badge $a[u]$, while $w$ still has $a[w] = a[u]$. So $v$ and $w$ become matching neighbors for that deal. Your earlier sum might have counted $w$’s subtree using a configuration that was best without prioritizing this new $v\text{--}w$ bonus, so you may need an incremental fix: add the profit increase from switching $w$’s subtree to the best arrangement compatible with the new top edge.
What if $w$ is not a child of $v$, but $w$ is a grandchild $v\text{--}m\text{--}w$ with $m \neq u$?
Answer to Hint 12: Then the relevant connection is not $v\text{--}w$ directly, but the edge $v\text{--}m$. After $v$ swaps with $u$, the badge at $v$ becomes $a[u]$. The subtree of $m$ might need a configuration where $m$ optionally swaps downward so that the badge at $m$ lines up with the new situation at $v$. That is what the per-child “(badge at child, best profit)” lists are for: you can look up the best profit for the needed resulting badge at $m$ after sorting those lists.
Why can you afford to run this DP over the whole tree for $n \le 10^5$?
Answer to Hint 13: Each vertex processes each incident edge a constant number of times; partner pointers are unique. Sorting the short lists at each node makes lookups efficient. Overall time is $O(n \log n)$ (the log comes from sorting small lists at vertices), and memory is linear in the tree size.
Implementation hygiene: precompute $\mathrm{partner}[i]$ for each vertex index $i$ by scanning the badge array twice. Root the tree, run DFS, combine children bottom-up. The final answer at the root is the better of “root does not swap with a child” and “root swaps with some child” (there is no parent swap at the root).