結果

問題 No.2258 The Jikka Tree
ユーザー gew1fw
提出日時 2025-06-12 17:14:39
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 4,417 bytes
コンパイル時間 339 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 298,784 KB
最終ジャッジ日時 2025-06-12 17:15:24
合計ジャッジ時間 40,508 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 7 WA * 11 TLE * 2 -- * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

sys.setrecursionlimit(1 << 25)

def main():
    input = sys.stdin.read
    data = input().split()
    ptr = 0

    N = int(data[ptr])
    ptr += 1

    # Read edges
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        u = int(data[ptr])
        v = int(data[ptr+1])
        ptr += 2
        edges[u].append(v)
        edges[v].append(u)

    # Read A array
    A = list(map(int, data[ptr:ptr+N]))
    ptr += N

    Q = int(data[ptr])
    ptr += 1

    queries = []
    for _ in range(Q):
        a_prime = int(data[ptr])
        b_prime = int(data[ptr+1])
        k_prime = int(data[ptr+2])
        delta = int(data[ptr+3])
        ptr +=4
        queries.append( (a_prime, b_prime, k_prime, delta) )

    # Precompute parent and children structure
    parent = [ -1 ] * N
    children = [[] for _ in range(N)]
    visited = [False] * N
    stack = [0]
    visited[0] = True
    while stack:
        u = stack.pop()
        for v in edges[u]:
            if not visited[v] and v != parent[u]:
                parent[v] = u
                children[u].append(v)
                visited[v] = True
                stack.append(v)

    # Function to compute subtree weights and find centroid
    def find_centroid(l, r, k):
        # Compute the weight for each node in [l, r)
        # Note: This is an array of weights, but in our case, the weights are based on A_w +k for w in [l, r)
        # So, for each node, the weight is (A_w +k) if l <= w < r else 0
        # We need to find the centroid based on these weights.
        # However, this is not the same as each node's weight; instead, the nodes outside [l, r) contribute 0.
        # So, our 'virtual' tree consists of nodes in [l, r), each with weight A_w +k.

        # We need to compute for each node, the sum of weights of nodes in its subtree (within [l, r))
        # This is a bit tricky because the subtree includes all descendants, but only those within [l, r).

        # We can perform a DFS starting from the root (or any node), and for each node, compute the sum of weights of its subtree within [l, r).

        # However, this is computationally expensive for each query. So, perhaps, for the sake of this problem, we can proceed with this approach, but it will not pass the time constraints.

        # For the purpose of this problem, we'll proceed with a simplified version.

        # Compute the total weight
        total_weight = 0
        for w in range(l, r):
            total_weight += A[w] + k

        # Now, perform a DFS to find the centroid
        # We can use any node as the starting point; for simplicity, we'll choose 0.

        # Compute subtree weights
        subtree_weights = [0] * N

        def dfs(u, parent_node):
            weight = 0
            if u >= l and u < r:
                weight += A[u] + k
            for v in children[u]:
                if v == parent_node:
                    continue
                dfs(v, u)
                weight += subtree_weights[v]
            subtree_weights[u] = weight

        dfs(0, -1)

        # Now find the centroid
        def find_centroid_helper(u, parent_node, half_total):
            max_sub = 0
            centroid = u
            for v in children[u]:
                if v == parent_node:
                    continue
                if subtree_weights[v] > max_sub:
                    max_sub = subtree_weights[v]
                    centroid = v
            if max_sub <= half_total:
                return u
            else:
                return find_centroid_helper(centroid, u, half_total)

        half_total = total_weight / 2
        centroid = find_centroid_helper(0, -1, half_total)

        return centroid

    # Process queries
    X = []
    sum_X = 0
    for i, (a_prime, b_prime, k_prime, delta) in enumerate(queries):
        if i == 0:
            a = a_prime
            b = b_prime
            k = k_prime
        else:
            a = (a_prime + sum_X) % N
            b = (b_prime + 2 * sum_X) % N
            k = (k_prime + (sum_X **2)) % 150001

        l = min(a, b)
        r = max(a, b) +1

        # Compute f and find v that minimizes it
        # In our approach, this is the centroid
        v = find_centroid(l, r, k)
        X.append(v)
        sum_X += v

    # Print the results
    for x in X:
        print(x)

if __name__ == '__main__':
    main()
0