Count changed nodes between two menu trees

You maintain a merchant menu as a rooted tree. Each node represents a menu item/category and has:

• key (string, unique among siblings)
• value (integer)
• children (0..k child nodes)

When a merchant sends a new menu tree, you want to count how many nodes have changed compared to the existing menu.

A node is considered changed if any of the following is true:

1. Removed (deactivated): A node exists in the old tree but does not exist in the new tree at the same position (i.e., under the same parent). Count every node in the removed subtree as changed.
2. Added: A node exists in the new tree but does not exist in the old tree at the same position . Count every node in the added subtree as changed.
3. Updated value: A node exists in both trees at the same position (same parent and same key ), but its value differs.

Important: If a node with the same key appears under a different parent in the new tree, treat this as removal of the old node (and its subtree) plus addition of the new node (and its subtree).

Task

Given the roots of the old and new trees, return the number of changed nodes.

Example 1

Old tree:

• a(1)
  • b(2)
    • d(4)
    • e(5)
  • c(3)
    • f(6)

New tree:

• a(1)
  • c(3)
    • f(66)

Output: 4

Explanation: b, d, e are removed (3 changes) and f value changes from 6 to 66 (1 change).

Example 2

Old tree:

• a(1)
  • b(2)
    • d(4)
    • e(5)
  • c(3)
    • g(7)

New tree:

• a(1)
  • b(2)
    • e(5)
    • d(4)
    • f(6)
  • h(8)
    • g(7)

Output: 5

Explanation: f is added (1). Subtree rooted at c is removed (c and its child g: 2). Subtree rooted at h is added (h and its child g: 2). Total = 1 + 2 + 2 = 5.

Constraints (you may assume)

• Total number of nodes across both trees up to 2 * 10^5 .
• Children order does not matter.
• key is unique among siblings (so children can be matched by key under the same parent).

Design an algorithm to compute the count efficiently.