Summary

In a tree-structured communication network, Aoki can cut at most \(1\) edge. After that, Takahashi will steal the maximum amount of data possible within a distance \(D\). We want to minimize this maximum stolen data amount.

For each edge cut, we can compute the remaining data quickly by subtracting the “amount of data that becomes unreachable on the other side due to the cut” from the “amount of data that could be stolen before the cut.”

Analysis

First, let \(S_x\) be the sum of the data amounts of vertices within distance \(D\) from each vertex \(x\) when no edges are cut.

[ S_x ]

If no edges are cut, Takahashi will choose the vertex \(x\) that maximizes \(S_x\), so the amount of stolen data is

[ \max_x S_x ]

---

Naively, every time we cut an edge, we would have to check the vertices within distance \(D\) for each potential intrusion vertex.

There are \(O(N)\) candidate edges to cut, \(O(N)\) potential intrusion vertices, and searching reachable vertices takes \(O(N)\) time. Thus, the total time complexity would be

[ O(N^3) ]

which is too slow for \(N \leq 3000\).

---

The key observation is that when a certain edge is cut, the only “lost vertices” are those on the opposite side of the cut edge.

Let us root the tree at an arbitrary vertex, say vertex \(1\).

Consider cutting the edge connecting parent \(p\) and child \(u\). Cutting this edge splits the tree into two parts:

• The subtree rooted at \(u\)
• The complement of the subtree

Suppose Takahashi’s intrusion vertex \(x\) is on the \(u\) side.

To reach any vertex \(y\) on the other side, Takahashi must pass through the edge \((p, u)\). Therefore, the distance in the original tree is

[

\operatorname{dist}(x,y)

\operatorname{dist}(x,u) + 1 + \operatorname{dist}(p,y) ]

Thus, the vertices on the other side that were originally within distance \(D\) from \(x\) are those satisfying:

[ \operatorname{dist}(p,y) \leq D - 1 - \operatorname{dist}(x,u) ]

This means that the amount of data lost on the other side due to the cut depends only on how far \(x\) is from \(u\).

For example, if \(D=5\) and \(x\) is at a distance of \(2\) from \(u\), the vertices on the other side that become unreachable are those satisfying:

[ \operatorname{dist}(p,y) \leq 5 - 1 - 2 = 2 ]

---

Therefore, we can group the vertices on the same side by their “distance from the endpoint of the cut edge.”

For the \(u\) side, if we can find for each distance \(t\):

• The maximum \(S_x\) among vertices at distance \(t\)
• The total data amount on the other side at distance \(D-1-t\) or less

then we can compute the maximum amount Takahashi can steal after the cut.

The same applies to the complement side.

Algorithm

1. Rooting the Tree

Perform a DFS starting from vertex \(1\) as the root, and for each vertex, find:

• Parent parent
• DFS order order
• Subtree size size

Using the DFS order, the subtree of a vertex \(u\) forms a contiguous range in order.

This allows us to easily list:

• The subtree side of \(u\)
• The other side

when the edge \((parent[u], u)\) is cut.

---

2. Computing All-Pairs Distances and \(S_x\)

Perform a DFS from each vertex \(s\) to find the distances to all other vertices.

Sum the data amounts of vertices within distance \(D\) to compute:

[ Ss = \sum{\operatorname{dist}(s,v) \leq D} V_v ]

The candidate answer when no edges are cut is:

[ \max_s S_s ]

---

3. Analyzing Each Edge Cut

Suppose we cut the edge \((p,u)\).

Let the \(u\) side be in and the complement side be out.

For the in side

Let \(x\) be a vertex on the in side, and let

[ t = \operatorname{dist}(u,x) ]

If \(t < D\), the vertices on the out side that become unreachable due to the cut are those satisfying:

[ \operatorname{dist}(p,y) \leq D - 1 - t ]

Subtracting this total data amount gives the amount of data Takahashi can steal starting from \(x\) after the cut:

[ S_x - (\text{total data amount on the out side within distance } D-1-t \text{ from } p) ]

If \(t \geq D\), reaching the other side requires a distance of at least \(D+1\), meaning no vertices on the other side were originally within distance \(D\). Thus, the stolen amount remains \(S_x\).

For the out side

Similarly, if \(x\) is on the out side and

[ t = \operatorname{dist}(p,x) ]

the vertices on the in side that become unreachable are those satisfying:

[ \operatorname{dist}(u,y) \leq D - 1 - t ]

---

4. Grouping by Distance

For each edge, we construct the following:

• in_ex[t]: The total data amount of vertices on the in side at distance \(t\) from \(u\)
• out_ex[t]: The total data amount of vertices on the out side at distance \(t\) from \(p\)
• md[t]: The maximum \(S_x\) among vertices on the in side at distance \(t\) from \(u\)
• mo[t]: The maximum \(S_x\) among vertices on the out side at distance \(t\) from \(p\)

Then, we compute the prefix sums of in_ex and out_ex.

This allows us to retrieve:

[ \text{total data amount on the out side within distance } k ]

in \(O(1)\) time.

---

5. Finding Takahashi’s Optimal Value for the Cut Edge

The maximum value Takahashi can obtain on the in side is:

[ \max_t \left(md[t] - out_ex[D-1-t]\right) ]

Similarly, on the out side, it is:

[ \max_t \left(mo[t] - in_ex[D-1-t]\right) ]

Since Takahashi can choose to intrude into either connected component after the edge is cut, the result of cutting this edge is:

[ \max(\text{maximum value on the in side}, \text{maximum value on the out side}) ]

Aoki wants to minimize this value, so we take the minimum over all edges.

Complexity

• Time Complexity: \(O(N^2)\)
• Space Complexity: \(O(N^2)\)

Computing all-pairs distances takes \(O(N^2)\) time.

For each edge, we construct the information by visiting all vertices once, which also takes \(O(N^2)\) in total.

Since we store all distance arrays, the space complexity is \(O(N^2)\).

Implementation Points

• The total data amount can be up to \(3000 \times 10^9 = 3 \times 10^{12}\), so long long is required in C++. In Python, integers have arbitrary precision, so this is not an issue.

• Since the depth of the tree can be up to \(N\), the code uses stack-based DFS instead of recursive DFS.

• By using the DFS order order and subtree sizes size, we can treat subtrees as contiguous intervals.

• Since vertices at distance \(D\) or more do not lose any vertices on the other side, we separately track only the maximum \(S_x\) for them.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N = data[0]
    D = data[1]
    V = data[2:2 + N]

    adj = [[] for _ in range(N)]
    idx = 2 + N
    for _ in range(N - 1):
        a = data[idx] - 1
        b = data[idx + 1] - 1
        idx += 2
        adj[a].append(b)
        adj[b].append(a)

    parent = [-1] * N
    parent[0] = -2
    order = []
    st = [0]
    while st:
        v = st.pop()
        order.append(v)
        pv = parent[v]
        for to in adj[v]:
            if to != pv:
                parent[to] = v
                st.append(to)
    parent[0] = -1

    size = [1] * N
    for v in reversed(order):
        p = parent[v]
        if p >= 0:
            size[p] += size[v]

    dist = []
    S = [0] * N
    for s in range(N):
        row = [0] * N
        st = [s]
        pst = [-1]
        while st:
            v = st.pop()
            pr = pst.pop()
            nd = row[v] + 1
            for to in adj[v]:
                if to != pr:
                    row[to] = nd
                    st.append(to)
                    pst.append(v)

        total = 0
        for i in range(N):
            if row[i] <= D:
                total += V[i]
        S[s] = total
        dist.append(row)

    ans = max(S)

    NN = N
    DD = D
    last = DD - 1
    ordr = order
    SS = S
    VV = V
    distm = dist
    par = parent
    sz = size

    for oi in range(1, NN):
        u = ordr[oi]
        p = par[u]
        l = oi
        r = oi + sz[u]

        rowu = distm[u]
        rowp = distm[p]

        in_ex = [0] * DD
        out_ex = [0] * DD
        md = [-1] * DD
        mo = [-1] * DD
        md_deep = -1
        mo_deep = -1

        for ii in range(l, r):
            x = ordr[ii]
            t = rowu[x]
            sx = SS[x]
            if t < DD:
                in_ex[t] += VV[x]
                if sx > md[t]:
                    md[t] = sx
            elif sx > md_deep:
                md_deep = sx

        for ii in range(l):
            x = ordr[ii]
            t = rowp[x]
            sx = SS[x]
            if t < DD:
                out_ex[t] += VV[x]
                if sx > mo[t]:
                    mo[t] = sx
            elif sx > mo_deep:
                mo_deep = sx

        for ii in range(r, NN):
            x = ordr[ii]
            t = rowp[x]
            sx = SS[x]
            if t < DD:
                out_ex[t] += VV[x]
                if sx > mo[t]:
                    mo[t] = sx
            elif sx > mo_deep:
                mo_deep = sx

        for i in range(1, DD):
            in_ex[i] += in_ex[i - 1]
            out_ex[i] += out_ex[i - 1]

        sub = md_deep
        comp = mo_deep

        for t in range(DD):
            rev = last - t

            m = md[t]
            if m >= 0:
                val = m - out_ex[rev]
                if val > sub:
                    sub = val

            m = mo[t]
            if m >= 0:
                val = m - in_ex[rev]
                if val > comp:
                    comp = val

        cur = sub if sub >= comp else comp
        if cur < ans:
            ans = cur

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.