Suppose that all bridges have already been built and that islands and bridges form not just a tree, but a chain.

Now the number of penguins on islands can be kept in an array of integers. If we build a Fenwick tree or interval tree over this array of integers, we can efficiently change the number of penguins on an island and calculate the sum of numbers in an interval. The commands penguins and excursion in this simpler variant can be processed in ~\mathcal O(\log N)~ time. The command bridge does not appear in this variant so the overall complexity is ~\mathcal O(Q \log N)~.

Now let the graph be a tree. In order to efficiently process penguins and excursion commands, we need to decompose the tree into a set of chains. There are many ways to do that, one of which (called heavy-light decomposition) is:

Choose an arbitrary node as the root of the tree. Now calculate for each node the number of nodes in its subtree. From each node with children, the child node with the largest degree is chosen and the edge connecting the parent and child is dubbed heavy. These heavy edges form chains. All other edges are called light.

This decomposition can be found in ~\mathcal O(N)~ time. An important property is that the number of heavy chains on the path from the root to any node is at most ~\log_2 N~. This is true because, any time we step off a heavy chain (move down a light edge), we at least halve the number of nodes in the current subtree.

Let depth(A) be the depth of node ~A~ in the tree.

Let dad(A) be the parent of node ~A~.

Let chain(A) be the chain node ~A~ is part of.

Let first(L) be the topmost node on chain ~L~.

The following algorithm calculates the number of penguins between nodes ~A~ and ~B~:

output = 0
while chain(A) ≠ chain(B):
    if depth(first(chain(A))) < depth(first(chain(B))):
        swap A and B
    output = output + chain(A).count(first(chain(A)), A)
    A = dad(first(chain(A)))
output = output + chain(A).count(A, B)

In other words, while ~A~ and ~B~ are not on the same chain, take the node on the deeper chain – call that node ~A~ and calculate the number of penguins on that chain (from the top to node ~A~). Then move ~A~ up to the first node not on that chain. Finally, when ~A~ and ~B~ are on the same chain, count the penguins between them.

By decomposing the tree and building a data structure over the vertices on each chain (as in the previously described simpler variant of the problem), the complexity of the penguins command remains ~\mathcal O(\log N)~, while the complexity of the excursion command becomes ~\mathcal O(\log^2 N)~. The overall complexity is ~\mathcal O(Q \log^2 N)~.

Now reintroduce the bridge command. For each component, we need to maintain some sort of decomposition into chains.

Let ~A~ and ~B~ be the nodes we need to connect. Choose the smaller of the two components (suppose node ~A~ is in that component), make the component rooted in ~A~ and find the heavy-light decomposition of the tree. Now connect node ~A~ as the child of node ~B~. This way in each component we still have some sort of decomposition. Unfortunately, this decomposition is not necessarily heavy-light because the sizes of subtrees in component ~B~ change, but the decomposition of the component does not change.

To fix this, we can rebuild the decomposition of a component when it becomes too unbalanced. One way to do this is to make the algorithm introspective – it can keep track of the number of steps needed to process penguins commands. When this number goes over ~\sqrt N~, we find the decomposition again. The overall complexity of the algorithm is ~\mathcal O(Q \sqrt N \log N)~.