You can solve this in $$$O(N \cdot \alpha(N))$$$ with a generalized dsu-forest (disjoint set union).

Consider processing the nodes in increasing order, storing for each node $$$n$$$ the connected component $$$c(n)$$$ containing it and (abstractly) the number of connected subgraphs $$$s(n)$$$ of that component containing that node. Then you can collect the answers as you go, as long as merging the components is made efficient enough.

Suppose for the sake of example you are processing node $$$7$$$ and its neighbors are nodes $$$2$$$ and $$$4$$$. (Larger merge operations are not very meaningfully harder.) Writing $$$s'(n)$$$ for what the abstract association $$$s(n)$$$ should be updated to, and $$$s(n)$$$ for its value before updating, it is clear that $$$s'(7) = s(2) * s(4)$$$, while for $$$n \in c(2)$$$, $$$s'(n) = s(n) * (1 + (1 + s(4)))$$$, and likewise for $$$n \in c(4)$$$, $$$s'(n) = s(n) * (1 + (1 + s(2)))$$$. Multiplying everything within each component by some constant is the tricky part, but can be done by using the dsu-forest itself to store factors of $$$s(n)$$$, which can be multiplied during the find operation when the value of $$$s(n)$$$ is needed. Care must be taken to ensure that the path-compression step preserves the path-products used for this calculation, and the merge step often has to allocate a new dsu-forest-node (rather than reuse one) for the same reason, but this should still be fairly easy to implement.

We still can do some dynamic programming. Let's choose a root, and let $$$T(v)$$$ be a subtree of node $$$v$$$ in a rooted tree.

For each node $$$x$$$ in $$$T(v)$$$ we would store a vector $$$dp_v(x)$$$ of size $$$3$$$:

• number of connected subgraphs inside $$$T(v)$$$ in which the maximum label is $$$x$$$;

• number of connected subgraphs inside $$$T(v)$$$ in which the maximum label is $$$x$$$ and $$$v$$$ belongs to subgraph;

• constant value $$$1$$$

For a subtree we would store all $$$dp_v(x)$$$ in some balanced binary tree (e.g. Cartesian tree). For each label $$$v$$$, answer could be found in a root as $$$dp_{root}(v)[0]$$$. Now we have to maintain this values.

Consider node $$$v$$$ with a list of children $$$c_1, c_2 \dots c_k$$$. Assume we store dp's for each of $$$c_i$$$ in corresponding balanced trees. First of all we want to add $$$v$$$ to each of $$$T(c_i)$$$.

• For $$$x < v$$$ we can't take $$$v$$$ into subgraph, so $$$dp_c'(x)[0] = dp_c(x)[0]$$$, $$$dp_c'(x)[1] = 0$$$.

• For $$$x > v$$$ we can take $$$v$$$ into subgraph, so $$$dp_c'(x)[0] = dp_c(x)[0] + dp_c(x)[1]$$$, $$$dp_c'(x)[1] = dp_c(x)[1]$$$.

• And $$$dp_v(v)[0] = dp_v(v)[1] = \sum_{x < v} dp_c(x)[1] + 1$$$.

After that we have to merge all $$$T(c_i)$$$. We would do it from small to large as usual. Consider we have two subtrees $$$|T(a)| > |T(b)|$$$.

First we will iterate over $$$x \in T(b)$$$ in increasing order, and we have

• $$$dp_v(x)[0] = dp_b(x)[0] + dp_b(x)[1] \sum_{y < x; y \in T(a)} dp_a(y)[0]$$$;

• $$$dp_v(x)[1] = dp_b(x)[1] \sum_{y < x; y \in T(a)} dp_a(y)[0]$$$

Now we have to symmetrically update values for labels from $$$T(a)$$$. For each segment of labels strictly between two consecutive $$$x_1, x_2 \in T(b)$$$ we have to set

• $$$dp_v(y)[0] = dp_a(y)[0] + dp_a(y)[1] \sum_{x_i < y} dp_b(x_i)[0]$$$;

• $$$dp_v(y)[1] = dp_a(y)[1] \sum_{x_i < y} dp_b(x_i)[0]$$$.

This range updates do not affect values for labels from $$$T(b)$$$.

What remains is to understand how we can perform all this range updates and range sums. In each node of the balanced tree we would store immediate vector $$$dp$$$, sum over all vectors in subtree $$$dpSum$$$, matrix of an update $$$dpUpdate$$$ that accumulates updates that should be performed on whole subtree. As far as matrix multiplication in associative and distributive we can accumulate updates and we can update $$$dpSum$$$.