Proving Solution Complexity

Problems and Contests
#1

In this problem, I found a solution that was different from the editorial.

Briefly, the editorial DP solution goes like this:

Root the tree at node 1.
Define f(u, x) as whether or not node “u” can have exactly x nodes reachable from it if we only consider the subtree of u.

For each v that is a child of u, we consider 3 cases:

  1. l[v]<l[u], if f(v, l[v]) is false, then the output of the test case is “NO”, because no matter what you do you cannot give node v a reachability of l[v]. It it’s true, we can either add l[v] nodes to be reachable by u (an arrow from u to v), or add no nodes from v to u (a closed arrow).

  2. l[v]>l[u]. This gives u a chance to “fix” v because theres either an open arrow from v to u or a closed arrow between them. If f(v, l[v]) and f(v, l[v]-l[u]) are both false, the output of the test case is “NO”. We will not change f[u] in this case.

  3. l[u]=l[v]. We can either have a closed arrow or an open 2-way arrow. We can merge the DP arrays to keep track of the possible reachability sizes of node u after considering the type of arrow between u and v.
    Let f'[u] be the updated dp. Then we set f'[u][x] to 0, then update:
    f'[u][x] |= f[u][i] && f[u][x-i], for all 1<=i<=x.

This will actually only have O(N^2) complexity because f[u][x] can only be true when there are at least x nodes in u’s subtree. We can then apply this trick.

Now for the linked solution I found, they solved it by considering every single connected component with equal values of l[u], so only cases 1 and 3 need to be handled by a component. However, not every node will be visited exactly once. Nodes “u” that are on the “border” of this component can still contribute l[u] to the siz of nodes in the component.

Screenshot 2026-09-26 at 12.00.17 AM
Screenshot 2026-09-26 at 12.00.17 AM1866×1756 122 KB

In the picture above, the middle black node contributes an extra y nodes to the components with l[u] of w, x, and z.

This makes we wonder why the runtime is still so fast, and whether its complexity is actually O(N^2).
In the normal subtree merging of two subtrees with size U and V, we can prove it like this:

Rewrite U with (1+1+… +1), a total of U ones. Rewrite V with (1+1+… +1), a total of V ones. Then the complexity of merging two subtrees is (1+1+…1) (1+1+…1). However, each pair of 1s on can only multiply at their LCA. After that they will be in the same subtree. Therefore we have at most O(N^2) pairs contributing to the total complexity.

In this solution, the siz of each node isn’t strictly bounded by the number of nodes in the component anymore, it can be increased by l[v] of node v next to the component of u, so is it still O(N^2) ?

Thanks,
Brian Zhao