Overview

This is a problem on a weighted tree where fire stations dynamically open and close, and we need to determine whether the distance from a given town to the nearest open fire station is at most \(T\).

To process each query efficiently, we perform centroid decomposition on the tree and maintain, for each centroid, “the distance from that centroid to the nearest open fire station.”

Analysis

What we want to find is, for each query of type 2 V T, whether

\[ \min_{x \in \text{open towns}} \mathrm{dist}(V, x) \]

is at most \(T\).

Naive methods are too slow

For example, if we run DFS / Dijkstra from town \(V\) for each query to find the nearest open fire station, it costs \(O(N)\) per query.

Since \(N, Q \leq 5 \times 10^4\), in the worst case this is

\[ O(NQ) \]

which is too slow.

Similarly, scanning all open fire stations and computing distances would also be too slow when the number of open stations is large.

Using Centroid Decomposition

For “dynamic nearest vertex queries” on trees, centroid decomposition is effective.

In centroid decomposition, we remove the centroid of the tree and recursively do the same for the remaining subtrees.

At this point, for each vertex \(v\), we precompute and store the centroids \(c\) related to \(v\) in the centroid decomposition, along with their distances

\[ \mathrm{dist}(v, c) \]

In centroid decomposition, the number of centroids each vertex is associated with is \(O(\log N)\).

Decomposition of Distances

For any two vertices \(u, v\), there exists a centroid \(c\) in the centroid decomposition that separates them.

For such a \(c\), the path from \(u\) to \(v\) in the original tree passes through \(c\), so

\[ \mathrm{dist}(u, v) = \mathrm{dist}(u, c) + \mathrm{dist}(v, c) \]

Therefore, the distance from town \(v\) to the nearest open fire station can be computed as:

\[ \min_{c \in \text{paths}[v]} \left( \mathrm{dist}(v, c) + \min_{x \in \text{open},\ c \in \text{paths}[x]} \mathrm{dist}(x, c) \right) \]

In other words, for each centroid \(c\), we need to maintain:

The minimum value of \(\mathrm{dist}(x, c)\) over all currently open fire stations \(x\).

Algorithm

1. Perform Centroid Decomposition

For each town \(v\), we store the following information:

\[ (c, \mathrm{dist}(v, c)) \]

Here, \(c\) is the centroid of the subtree that \(v\) belongs to in the centroid decomposition.

In the code, this information is stored in paths[v].

For example,

paths[v] = [c1, d1, c2, d2, ...]

where centroids and distances are stored alternately.

The number of centroids stored for each vertex is \(O(\log N)\).

2. Maintain distances to open fire stations for each centroid

For each centroid \(c\), we want to maintain the following multiset:

\[ \{\mathrm{dist}(x, c) \mid x \text{ is an open fire station}\} \]

If we can find the minimum of this, we can use it when answering queries.

However, since fire stations can be closed, we need to support deletion of values.

Python’s heapq is fast for retrieving the minimum but poor at deleting arbitrary values.

Therefore, we use the following two heaps:

• add_heaps[c]: added distances
• del_heaps[c]: distances scheduled for deletion

When we want to delete a value, we actually just insert it into del_heaps[c].

Right before checking the minimum, we do:

while add_heaps[c] and del_heaps[c] and add_heaps[c][0] == del_heaps[c][0]:
    heappop(add_heaps[c])
    heappop(del_heaps[c])

to remove values that have been deleted all at once.

This is a technique called lazy deletion.

3. Initial State

In the initial state, only the fire station at town \(1\) is open.

Therefore, for all centroids \(c\) contained in paths[1], we add

\[ \mathrm{dist}(1, c) \]

to add_heaps[c].

4. Type 1 X

Toggle the state of the fire station at town \(X\).

If closed, open it

For each centroid \(c\) in paths[X], add

\[ \mathrm{dist}(X, c) \]

to add_heaps[c].

If open, close it

Similarly, for each centroid \(c\), add

\[ \mathrm{dist}(X, c) \]

to del_heaps[c].

The actual deletion is performed later when we look at the minimum for that centroid.

5. Type 2 V T

Determine whether the distance from town \(V\) to the nearest open fire station is at most \(T\).

For each centroid \(c\) in paths[V], consider:

\[ \mathrm{dist}(V, c) + \min_{x \text{ open}} \mathrm{dist}(x, c) \]

If this is at most \(T\), the answer is YES.

In the code,

rem = T - dist(V, c)

is computed, and we check whether there exists an open fire station within distance rem from centroid \(c\).

If no centroid satisfies the condition, the answer is NO.

Complexity

• Time complexity: \(O(N \log N + Q \log N \log (N+Q))\) amortized
• Space complexity: \(O((N+Q) \log N)\)

Due to centroid decomposition, the number of centroids each vertex has is \(O(\log N)\).

For each event, we only need to look at at most \(O(\log N)\) centroids, and heap operations cost \(O(\log (N+Q))\).

Also, values removed by lazy deletion are each popped at most once, so the overall complexity is bounded in an amortized sense.

Implementation Notes

• The maximum distance can be large, so in C++ etc., long long is necessary.

  • In Python, there is no need to worry about integer overflow.

• The fire station at town \(1\) is always open, and town \(1\) never appears in type 1 queries in the input.

• Since heapq does not support arbitrary deletion, we use lazy deletion with add_heaps and del_heaps.

• paths[v] stores pairs of (centroid, distance).

  • In the code, for efficiency, instead of a list of tuples, it is stored in the form [c, d, c, d, ...].

• Since centroid decomposition uses recursion, in Python it is safe to set sys.setrecursionlimit to a large value.

  Source Code

import sys
from heapq import heappush, heappop

def main():
    input = sys.stdin.buffer.readline
    sys.setrecursionlimit(200000)

    N, Q = map(int, input().split())
    g = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        a, b, c = map(int, input().split())
        g[a].append((b, c))
        g[b].append((a, c))

    blocked = [False] * (N + 1)
    parent = [0] * (N + 1)
    size = [0] * (N + 1)
    paths = [[] for _ in range(N + 1)]

    def decompose(start):
        order = []
        stack = [start]
        parent[start] = 0

        while stack:
            v = stack.pop()
            order.append(v)
            pv = parent[v]
            for to, _ in g[v]:
                if to != pv and not blocked[to]:
                    parent[to] = v
                    stack.append(to)

        for v in reversed(order):
            s = 1
            pv = parent[v]
            for to, _ in g[v]:
                if to != pv and not blocked[to]:
                    s += size[to]
            size[v] = s

        total = len(order)
        half = total // 2
        centroid = -1

        for v in order:
            mx = total - size[v]
            for to, _ in g[v]:
                if not blocked[to] and parent[to] == v:
                    if size[to] > mx:
                        mx = size[to]
            if mx <= half:
                centroid = v
                break

        c = centroid
        blocked[c] = True

        stack = [(c, 0, 0)]
        while stack:
            v, p, d = stack.pop()
            paths[v].append(c)
            paths[v].append(d)
            for to, w in g[v]:
                if to != p and not blocked[to]:
                    stack.append((to, v, d + w))

        for to, _ in g[c]:
            if not blocked[to]:
                decompose(to)

    decompose(1)

    g = blocked = parent = size = None

    add_heaps = [[] for _ in range(N + 1)]
    del_heaps = [[] for _ in range(N + 1)]
    active = [False] * (N + 1)
    active[1] = True

    p = paths[1]
    for i in range(0, len(p), 2):
        heappush(add_heaps[p[i]], p[i + 1])

    out = []

    for _ in range(Q):
        s = input().split()

        if s[0] == b'1':
            x = int(s[1])
            p = paths[x]

            if active[x]:
                active[x] = False
                for i in range(0, len(p), 2):
                    heappush(del_heaps[p[i]], p[i + 1])
            else:
                active[x] = True
                for i in range(0, len(p), 2):
                    heappush(add_heaps[p[i]], p[i + 1])

        else:
            v = int(s[1])
            T = int(s[2])
            p = paths[v]
            ok = False

            i = 0
            lp = len(p)
            while i < lp:
                c = p[i]
                d = p[i + 1]
                rem = T - d

                if rem >= 0:
                    ah = add_heaps[c]
                    dh = del_heaps[c]

                    while ah and dh and ah[0] == dh[0]:
                        heappop(ah)
                        heappop(dh)

                    if ah and ah[0] <= rem:
                        ok = True
                        break

                i += 2

            out.append("YES" if ok else "NO")

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.