1. Identifiable Positions from Range-Sum Queries

Problem Description

You are given a hidden array a of length n, but its values are unknown.

You are given m queries, where each query is [l, r]. For every query, you know the value:

a[l] + a[l+1] + ... + a[r]

Your task is to return the sorted list of positions i whose individual value a[i] can be uniquely determined from the given range-sum queries.

You don't need to actually calculate the values of a[i]; only return the positions that are identifiable.

Example

Suppose:

n = 9

queries:
[1,9]
[2,9]
[2,3]
[2,5]
[2,8]
[7,8]
[7,9]
[4,9]

The answer is:

[1, 6, 9]

Approach

The key is to use prefix sums.

Define:

P[0] = 0
P[i] = a[1] + a[2] + ... + a[i]

Then:

a[i] = P[i] - P[i-1]

A query [l, r] gives us:

a[l] + ... + a[r] = P[r] - P[l-1]

So every query gives a known difference between two prefix sums:

P[l-1] ---- P[r]

We can therefore represent every query as an edge between vertices l-1 and r.

Now, to determine a[i], we need:

a[i] = P[i] - P[i-1]

If P[i-1] and P[i] are connected through the graph, the known differences along the path can be combined to determine their difference.

Therefore:

a[i] is identifiable iff prefix nodes i-1 and i belong to the same connected component.

This makes DSU / Union-Find a natural solution.

Complexity

There are n+1 prefix nodes (0 ... n) and m edges.

Using DSU with path compression and union by size:

Time:  O((n + m) α(n))
Space: O(n)

which is effectively O(n + m).

Python

n=int(input())
m=int(input())
queries=[]
for _ in range(m): queries.append([int(x) for x in input().split()])
parent = list(range(n + 1))
size = [1] * (n + 1)
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x
def union(a, b):
    a = find(a)
    b = find(b)
    if a == b:
        return
    if size[a] < size[b]:
        a, b = b, a
    parent[b] = a
    size[a] += size[b]
# Query [l, r] tells us:
# prefix[r] - prefix[l-1] is known
# So connect l-1 and r
for l, r in queries:
    union(l - 1, r)
ans = []
# a[i] = prefix[i] - prefix[i-1]
# We can determine it iff prefix[i] and prefix[i-1]
# belong to the same component.
for i in range(1, n + 1):
    if find(i - 1) == find(i):
        ans.append(i)
print(ans)

Core idea in one line

[l,r] → P[r] - P[l-1] → union(l-1, r)

Then:

find(i-1) == find(i) → a[i] is identifiable

2. Maximum Weight Subset of a Tree with No Ancestor-Descendant Pair

I came across this tree-DP problem in an OA and couldn't find an exact LeetCode equivalent.

Problem Description

You are given a rooted tree with n nodes numbered 1 ... n.

• The root is always node 1.
• You are given arrays from and to describing the directed edges from[i] -> to[i].
• Each node i has a weight wt[i].

Choose a subset of nodes such that:

No two selected nodes have an ancestor-descendant relationship.

In other words, if node u is an ancestor of node v, you cannot select both u and v.

Return the maximum possible sum of weights of the selected nodes.

n can be as large as 10^5, so the solution needs to be approximately O(n).

Example

Consider:

        1(10)
       /     \
    2(5)     3(6)
    /  \       \
 4(20) 5(3)    6(15)

One optimal subset is:

{4, 5, 6}

with sum:

20 + 3 + 15 = 38

We cannot select {1, 4} because 1 is an ancestor of 4.

Similarly, we cannot select {2, 4} because 2 is an ancestor of 4.

However, nodes 4, 5, and 6 can all be selected because they are in different branches / are not ancestors of one another.

Approach — Tree DP

For every node u, let:

dp[u] = maximum weight of a valid subset inside the subtree of u

There are two possibilities.

1. Select u

If we select u, then we cannot select any descendant of u.

Therefore:

take = wt[u]

Notice this is different from the usual "no adjacent nodes" tree DP.

We aren't just preventing selection of the children — the entire subtree becomes unavailable.

2. Don't select u

If we don't select u, we can independently select the optimal valid subset from each child's subtree.

Therefore:

skip = dp[child1] + dp[child2] + ...

So:

dp[u] = max(
    wt[u],
    sum(dp[v] for v in children[u])
)

Finally:

answer = dp[1]

Why does this handle distant descendants?

Consider:

1
|
3
|
4

At node 3:

dp[3] = max(
    wt[3],
    dp[4]
)

Suppose dp[3] chooses 4.

Then at node 1:

dp[1] = max(
    wt[1],
    dp[3]
)

It chooses either node 1 or the best solution inside its subtree.

It never combines:

{1} + {4}

because wt[1] and dp[3] are the two alternatives of the max.

Thus, an ancestor and any descendant, regardless of distance, can never both be selected.

Python Solution

Since n can be 10^5, I avoid recursive DFS because a tree can be a chain and exceed Python's recursion limit.

def solve(n, from_, to, wt):
    children = [[] for _ in range(n + 1)]

    # Build the rooted tree
    for i in range(n - 1):
        u = from_[i]
        v = to[i]
        children[u].append(v)

    # Root is always 1
    # Create parent-before-child order
    order = [1]

    for u in order:
        for v in children[u]:
            order.append(v)

    dp = [0] * (n + 1)

    # Process children before parents
    for u in reversed(order):

        # Select u:
        # no descendant of u can be selected
        take = wt[u - 1]

        # Don't select u:
        # independently solve each child subtree
        skip = 0
        for v in children[u]:
            skip += dp[v]

        dp[u] = max(take, skip)

    return dp[1]

Complexity

Each node and edge is processed a constant number of times.

Time:  O(n)
Space: O(n)

Key Insight

The recurrence can be summarized as:

                    dp[u]
                   /     \
             take u      skip u
                |           |
             wt[u]      Σ dp[child]
                |
       entire subtree
       becomes unavailable

So the important difference from House Robber III is:

House Robber III:
take u → cannot take children

This problem:
take u → cannot take ANY descendant

dp[u] = max(wt[u], sum(dp[child]))

My friend got these two problems in their OA:

• LeetCode 3367 — Maximize Sum of Weights after Edge Removals (LeetCode)
• CSES 1746 — Array Description (cses.fi)