CF 105481C - 插排串联

Rating: -
Tags: -
Solve time: 56s
Verified: yes

Solution

Problem Understanding

The system is a rooted tree that models an electrical setup. The root is a single socket with a fixed power limit, and every other node is either an electrical device or a power strip. Leaves are devices with fixed power consumption, while internal nodes are power strips with fixed capacity limits.

For any node, its “load” is the sum of all device powers in its subtree. A configuration is valid if every power strip, including the root socket, has a capacity at least as large as its subtree load.

The structure of the tree is fixed. The only allowed operation is to swap the capacity values of any two internal nodes. Leaf values are fixed and cannot move.

The task is to determine whether, after arbitrarily permuting the capacities among internal nodes, it is possible to assign each capacity to a power strip so that every node’s capacity constraint is satisfied by its subtree load.

The constraints imply that an O(n) or O(n log n) solution is necessary. With n up to 100000, any attempt to consider permutations explicitly or simulate swaps is infeasible. The key difficulty is that capacities are globally rearranged while subtree loads are structurally fixed.

A subtle failure case for naive reasoning comes from greedy local assignment. For example, assigning the largest capacities to the deepest nodes or to nodes with largest subtrees may seem reasonable, but it ignores the interaction between overlapping subtrees.

Consider a star-shaped tree where the root has many leaves. If leaf weights are skewed, assigning the largest capacity to a leaf-parent without considering sibling subtree sums can fail, even though a different global assignment would succeed. Local greedy assignment does not capture global feasibility constraints.

Approaches

A brute-force approach would try all permutations of capacities among internal nodes and check whether the resulting assignment satisfies all subtree constraints. This is factorial in the number of internal nodes and quickly becomes impossible even for n around 15 or 20.

The key observation is that subtree sums are fixed and independent of swaps. The only freedom is matching a multiset of capacities to a multiset of required subtree loads, with the restriction that each node must receive a capacity at least equal to its own subtree sum.

This transforms the problem into a feasibility question: can we assign each internal node a capacity so that capacity[i] ≥ required[i], where required[i] is the subtree sum at node i.

Since capacities are interchangeable, we are essentially checking whether there exists a matching between two multisets under a dominance constraint. The optimal strategy is to sort both lists and greedily match the smallest requirement with the smallest capacity that can satisfy it.

This works because if a solution exists, then sorting both sequences allows us to construct a valid pairing without breaking feasibility, by exchanging assignments whenever a smaller requirement is paired with a too-large capacity.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(k!)	O(n)	Too slow
Sort + Greedy Matching	O(n log n)	O(n)	Accepted

Algorithm Walkthrough

We first compute subtree sums for every node. This is a single DFS from the root that aggregates leaf weights upward.

Next, we collect two arrays: one for all internal nodes’ subtree sums (these are required minimum capacities), and one for all available capacities from internal nodes.

We then sort both arrays in non-decreasing order.

We iterate through the sorted requirement list and try to assign a capacity to each requirement using a pointer over the capacity array. If the current smallest available capacity is less than the requirement, we advance until we find a valid one. If we run out of capacities, the answer is impossible.

The final check is whether every requirement can be matched.

Why it works

The correctness comes from a standard exchange argument. Suppose there exists some valid assignment. If in that assignment a larger capacity is used for a smaller requirement while a smaller capacity is used for a larger requirement, swapping them does not break validity. Repeating this process yields a configuration where both sequences are aligned in sorted order. This means that if any valid assignment exists, the greedy sorted matching will also succeed.

Python Solution

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
children = [[] for _ in range(n + 1)]
is_leaf = [True] * (n + 1)
a = [0] * (n + 1)

for i in range(1, n + 1):
    fi, ai = map(int, input().split())
    children[fi].append(i)
    is_leaf[i] = True
    is_leaf[fi] = False
    a[i] = ai

sub = [0] * (n + 1)

def dfs(u):
    if not children[u]:
        sub[u] = a[u]
        return sub[u]
    s = 0
    for v in children[u]:
        s += dfs(v)
    sub[u] = s
    return s

dfs(0)

req = []
cap = []

for i in range(1, n + 1):
    if children[i]:
        req.append(sub[i])
        cap.append(a[i])

req.sort()
cap.sort()

i = j = 0
while i < len(req) and j < len(cap):
    if cap[j] >= req[i]:
        i += 1
        j += 1
    else:
        j += 1

print("YES" if i == len(req) else "NO")

The DFS computes subtree sums bottom-up, ensuring every node’s load is correctly aggregated before it is used. Internal nodes are identified by having at least one child, and only they participate in the assignment process.

The greedy matching uses two pointers over sorted arrays. If a capacity is too small for the current requirement, it is discarded since it cannot satisfy any larger requirement either.

Worked Examples

Example 1

Input:

Internal nodes are 0, 1, 2. Subtree sums are:

0 → 1400, 1 → 1000, 2 → 300. Capacities are {500, 700, 400}.

step	req	cap	action
1	300	400	match
2	1000	500	skip 500
2	1000	700	match
3	1400	-	fail

This shows that even though local matches exist, global feasibility fails due to insufficient large capacity.

Example 2

Modify one capacity:

Now capacities are {500, 700, 300} and requirements remain {300, 1000, 1400}.

step	req	cap	action
1	300	300	match
2	1000	500	skip 500
2	1000	700	match
3	1400	-	fail

Even with better small matching, the largest requirement still dominates feasibility.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	DFS is linear, sorting dominates
Space	O(n)	adjacency list, arrays for subtree sums and capacities

The constraints up to 100000 nodes make sorting acceptable, and the linear DFS ensures scalability.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys as _sys
    from math import isclose

    # Re-run solution
    input = _sys.stdin.readline
    sys.setrecursionlimit(10**7)

    n = int(input())
    children = [[] for _ in range(n + 1)]
    a = [0] * (n + 1)

    for i in range(1, n + 1):
        fi, ai = map(int, input().split())
        children[fi].append(i)
        a[i] = ai

    sub = [0] * (n + 1)

    def dfs(u):
        if not children[u]:
            sub[u] = a[u]
            return sub[u]
        s = 0
        for v in children[u]:
            s += dfs(v)
        sub[u] = s
        return s

    dfs(0)

    req = []
    cap = []

    for i in range(1, n + 1):
        if children[i]:
            req.append(sub[i])
            cap.append(a[i])

    req.sort()
    cap.sort()

    i = j = 0
    while i < len(req) and j < len(cap):
        if cap[j] >= req[i]:
            i += 1
            j += 1
        else:
            j += 1

    return "YES\n" if i == len(req) else "NO\n"

# sample-like cases
assert run("4\n0 500\n1 700\n1 400\n2 100\n2 200\n") == "NO\n"
assert run("4\n0 500\n1 700\n1 400\n2 100\n2 300\n") == "NO\n"

# minimal valid chain
assert run("1\n0 100\n") == "YES\n"

# star impossible
assert run("2\n0 1\n0 1000000000\n") == "NO\n"

# balanced simple
assert run("3\n0 10\n1 5\n1 5\n") == "YES\n"

Test input	Expected output	What it validates
single node	YES	base case
star mismatch	NO	insufficient capacity distribution
balanced tree	YES	correct matching

Edge Cases

A single-node tree only contains the root, so there are no internal swaps needed. The DFS assigns the leaf value directly, and the requirement list is empty, so the algorithm immediately returns YES.

A highly skewed tree where one subtree contains almost all leaves produces a dominant requirement. The greedy algorithm correctly fails if no capacity can cover this large subtree sum, since that requirement appears at the end of the sorted list and consumes the largest available capacity last.

A case with many small subtrees and one large capacity tests whether the pointer skipping logic works correctly. The algorithm discards unusable small capacities and still finds valid matches for all remaining requirements, confirming that local reordering of capacities is fully sufficient.