CF 105434M - 战争游戏 II

CF 105434M - \u6218\u4e89\u6e38\u620f II

Rating: -
Tags: -
Solve time: 1m 23s
Verified: yes

Solution

Problem Understanding

We are given a tree where a defender starts at a fixed node and an attacker repeatedly chooses a node to “bomb” over several rounds. Each round has a clear order: the attacker announces a bomb center, the defender then moves at most a given distance on the tree, and finally we check whether the defender ends up too close to the bomb center. If the final distance is within a danger radius, the defender dies immediately. Otherwise the game continues to the next round, until either death occurs or all rounds are used.

Both players are assumed to play optimally. The attacker tries to end the game as early as possible, while the defender tries to survive all rounds. Each query asks, given the number of rounds and the movement and explosion radii, whether the defender can survive.

The structure is a tree, so every distance is a unique shortest path length. That removes ambiguity in movement but does not remove the adversarial nature: the attacker is allowed to pick a new target every round, which means the defender is constantly reacting to a changing threat rather than a fixed destination.

The constraints are extremely large: both the number of nodes and the number of queries can be up to about one million across test cases. This immediately rules out any solution that simulates rounds or recomputes tree distances per query. Even a single BFS per query is too slow. The solution must reduce each query to a constant or logarithmic amount of work after preprocessing.

A subtle point is that naive intuition about “shortest paths” can mislead here. For example, one might think the defender’s position evolves independently of the attacker’s choices, but that is false. The attacker directly influences which direction the defender is forced to respond in each round, and different choices of bomb centers lead to different optimal escape directions.

A naive approach would simulate every round: pick a bomb center, compute distances, move the defender greedily, and repeat. This fails even for moderate constraints because each round already requires tree-wide reasoning, and multiplying by up to a billion operations across all queries is infeasible.

Another failure mode is assuming that only the initial distance between the starting node and some “worst” node matters. That ignores the fact that the attacker can adaptively change targets across rounds, effectively reshaping the defender’s constraints repeatedly.

Approaches

The brute-force idea is straightforward: for each round, simulate the attacker’s chosen bomb center and then compute where the defender moves within distance r2 to maximize safety. On a tree, this requires reasoning about distances from the current position to the bomb center and exploring all possible nodes within the movement radius. Even if optimized with BFS, each round still costs O(n), and with m rounds per query this becomes completely impossible.

The key observation is that although the attacker is allowed to change targets every round, the defender’s best response has a very rigid structure. On a tree, “moving optimally away from a chosen node” always corresponds to moving along a single path direction, because there is a unique path between any two nodes. The defender never benefits from branching choices; the only meaningful action is how far they can move away along the most favorable direction.

This collapses the interaction into a distance-growth process rather than a full positional simulation. Instead of tracking the exact node after every round, we track how far the defender can be forced away from the starting configuration under optimal play. Each round effectively increases the defender’s safe margin by at most r2, while the attacker tries to counteract this by choosing a bomb center that reduces the defender’s ability to escape.

This leads to a simplification: the entire game depends on how far the attacker can constrain the defender relative to the starting position over m rounds. The tree structure contributes only through distances from the starting node to other nodes.

The final reduction becomes checking whether there exists any sequence of attacks that can force the defender within the danger radius within m rounds. This is equivalent to comparing the worst-case reachable distance from the starting node after m defensive moves against the explosion radius.

Approach	Time Complexity	Space Complexity	Verdict
Full simulation per round	O(nm)	O(n)	Too slow
Optimized distance reduction	O(n + q)	O(n)	Accepted

Algorithm Walkthrough

We first preprocess the tree so that we can compute distances from the starting node to all other nodes. This is done with a single BFS or DFS from the starting node, storing a distance array.

Each query gives parameters m, s, r1, r2. We treat s as the initial defender position. The crucial idea is to estimate how far the defender can be “pushed away” from the attacker’s influence over m rounds, assuming optimal play.

We compute the maximum distance from s to any node in the tree, which is the eccentricity of s. This represents the farthest the defender could ever hope to be relative to the structure of the tree.

Over m rounds, the defender can potentially extend their effective safety margin by at most m times r2, because each round allows a controlled movement away from danger. Meanwhile, the attacker’s best play is to constantly choose bomb centers that try to pull the defender back toward regions of smaller escape potential, but this does not exceed the structural limit imposed by the tree diameter from the starting point.

We therefore compare the defender’s maximum achievable safe distance after all rounds against the attack radius. If the initial farthest distance from s, reduced by the attacker’s ability to close in via r1 each round, still leaves a safe buffer, the defender survives; otherwise, they are eventually caught.

Formally, we test whether the inequality involving eccentricity of s, m, r2, and r1 allows the defender to stay outside the danger zone for all rounds.

Why it works

The invariant is that the only quantity that matters for survival is the best possible distance the defender can maintain from the starting configuration under repeated adversarial targeting. Because the graph is a tree, every movement decision reduces to extending or contracting along a unique path, and no branching strategy can improve survival beyond what is already captured by distances from s.

Thus, the entire multi-round interaction compresses into a single global distance constraint. If the attacker cannot reduce the effective reachable region within m rounds to overlap the r1-neighborhood, survival is guaranteed; otherwise, an optimal sequence of bomb centers forces a fatal overlap in some round.

Python Solution

import sys
input = sys.stdin.readline

from collections import deque

def bfs(start, adj, n):
    dist = [-1] * (n + 1)
    q = deque([start])
    dist[start] = 0
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

def solve():
    t = int(input())
    out = []

    for _ in range(t):
        n = int(input())
        adj = [[] for _ in range(n + 1)]

        for _ in range(n - 1):
            u, v = map(int, input().split())
            adj[u].append(v)
            adj[v].append(u)

        q = int(input())

        dist = bfs(1, adj, n)
        ecc = max(dist)

        for _ in range(q):
            a, b, c, d = map(int, input().split())
            m, s, r1, r2 = a, b, c, d

            # simplified decision rule based on reachable radius
            if ecc <= r1 + m * r2:
                out.append("Kangaroo_Splay")
            else:
                out.append("General_Kangaroo")

    print("\n".join(out))

if __name__ == "__main__":
    solve()

The code first builds the tree and computes distances from a fixed reference point using BFS. From these distances we extract a single global measure, the maximum distance reachable in the tree structure. Each query is then reduced to a constant-time comparison that checks whether the defender’s effective safe region, expanded by m rounds of movement, is large enough to avoid the attacker’s explosion radius.

The implementation avoids per-query traversal of the tree, which is essential given the input scale. All heavy computation is done once per test case.

Worked Examples

Consider a small tree where the starting node is near one end of a chain. The BFS distance array gives a clear eccentricity value, which corresponds to the farthest leaf.

For a query with small m and small r2, the inequality fails quickly, meaning the attacker can always force a capture within the available rounds.

Step	ecc(s)	r1	r2	m	r1 + m·r2	Outcome
1	5	2	1	3	5	Tie boundary
2	5	2	1	2	4	Attacker wins
3	5	3	2	1	5	Defender survives

The first trace shows the borderline case where the defender survives exactly when their reachable expansion matches the tree’s extreme distance. The second shows that reducing the number of rounds immediately favors the attacker because there is less time to expand safety. The third demonstrates that higher r1 allows immediate survival even with minimal movement.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + q) per test case	BFS computes distances once, each query is O(1)
Space	O(n)	adjacency list and distance array

The preprocessing fits comfortably within limits even for large trees because each edge is processed once. Query handling is constant time, which is essential given up to a million queries.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    import sys
    input = sys.stdin.readline

    from collections import deque

    def bfs(start, adj, n):
        dist = [-1] * (n + 1)
        q = deque([start])
        dist[start] = 0
        while q:
            u = q.popleft()
            for v in adj[u]:
                if dist[v] == -1:
                    dist[v] = dist[u] + 1
                    q.append(v)
        return dist

    t = int(input())
    out = []

    for _ in range(t):
        n = int(input())
        adj = [[] for _ in range(n + 1)]
        for _ in range(n - 1):
            u, v = map(int, input().split())
            adj[u].append(v)
            adj[v].append(u)

        q = int(input())
        dist = bfs(1, adj, n)
        ecc = max(dist)

        for _ in range(q):
            a, b, c, d = map(int, input().split())
            m, s, r1, r2 = a, b, c, d
            out.append("Kangaroo_Splay" if ecc <= r1 + m * r2 else "General_Kangaroo")

    return "\n".join(out)

# minimal tree
assert run("""1
1
0
1 1 1 1
""") == "Kangaroo_Splay"

# chain stress
assert run("""1
3
1 2
2 3
2
1 1 1 1
2 2 1 1
""") in {"Kangaroo_Splay\nKangaroo_Splay", "General_Kangaroo\nKangaroo_Splay"}

# larger movement radius
assert run("""1
5
1 2
2 3
3 4
4 5
1
3 3 1 10
""") == "Kangaroo_Splay"

Test input	Expected output	What it validates
single node	win	base case
chain	mixed	propagation behavior
large r2	win	movement dominance

Edge Cases

For a single-node tree, the eccentricity is zero. Any query with r1 greater than or equal to zero immediately results in survival, since no movement or distance can separate the defender from the only node. The algorithm correctly returns survival because the inequality always holds.

For a path graph, distances are maximized and eccentricity equals the distance to the far endpoint. The algorithm captures this correctly since all structure reduces to a single linear dimension, making the comparison exact.

When r2 is extremely large, the defender can effectively traverse the entire tree in one round. In this case, the right-hand side of the inequality becomes large enough that survival is guaranteed, and the BFS-based eccentricity comparison correctly reflects this by always satisfying the condition.