結果

問題 No.898 tri-βutree
ユーザー shotoyooshotoyoo
提出日時 2021-07-17 18:00:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,601 ms / 4,000 ms
コード長 3,128 bytes
コンパイル時間 385 ms
コンパイル使用メモリ 87,244 KB
実行使用メモリ 171,712 KB
最終ジャッジ日時 2023-09-21 11:20:53
合計ジャッジ時間 27,517 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 866 ms
171,712 KB
testcase_01 AC 70 ms
71,128 KB
testcase_02 AC 84 ms
76,372 KB
testcase_03 AC 79 ms
75,912 KB
testcase_04 AC 79 ms
75,704 KB
testcase_05 AC 81 ms
76,404 KB
testcase_06 AC 81 ms
75,824 KB
testcase_07 AC 1,534 ms
162,952 KB
testcase_08 AC 1,536 ms
163,944 KB
testcase_09 AC 1,459 ms
167,392 KB
testcase_10 AC 1,489 ms
163,136 KB
testcase_11 AC 1,547 ms
163,012 KB
testcase_12 AC 1,601 ms
164,324 KB
testcase_13 AC 1,509 ms
164,256 KB
testcase_14 AC 1,541 ms
164,540 KB
testcase_15 AC 1,538 ms
164,052 KB
testcase_16 AC 1,531 ms
164,348 KB
testcase_17 AC 1,509 ms
163,508 KB
testcase_18 AC 1,578 ms
161,860 KB
testcase_19 AC 1,511 ms
161,336 KB
testcase_20 AC 1,461 ms
167,332 KB
testcase_21 AC 1,574 ms
163,576 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda : sys.stdin.readline().rstrip()

sys.setrecursionlimit(2*10**5+10)
write = lambda x: sys.stdout.write(x+"\n")
debug = lambda x: sys.stderr.write(x+"\n")
writef = lambda x: print("{:.12f}".format(x))

# 木の読み込み・重みあり
n = int(input())
ns = [[] for _ in range(n)]
vs = [0]*n
for _ in range(n-1):
    u,v,c = map(int, input().split())
    ns[u].append((c,v))
    ns[v].append((c,u))
    
"""木におけるダブリングdouble
祖先と何かを同時に求める
"""
# 深さ
def cdepth(ns, root=0):
    # rootを根としたときの深さ
    ps = [None] * n
    ps[root] = -1
    q = [0]
    while q:
        u = q.pop()
        for c,v in ns[u]:
            if ps[v] is None:
                ps[v] = u
                vs[v] = c
                q.append(v)
    # psを元から持っている場合、引数のnsをpsにしてこの下だけで良い
    depth = [None] * len(ps)
    ns = [[] for _ in range(len(ps))]
    for i,p in enumerate(ps):
        ns[p].append(i)
    depth[root] = 0
    q = [root]
    while q:
        u = q.pop()
        for v in ns[u]:
            if depth[v] is None:
                depth[v] = depth[u] + 1
                q.append(v)
    return depth, ps

# ダブリング
def double(ps, vs=None):
    # global: n=psのサイズ
    prev = [[None]*n for _ in range(k)] # prev[i][j]: jから2^i個上の上司
    vals = [[None]*n for _ in range(k)] # vals[i][j]: jから2^i個上の上司までの間の枝重みのmax
    for j in range(n):
        prev[0][j] = ps[j]
        vals[0][j] = vs[j]
    for i in range(1,k):
        for j in range(n):
            p = prev[i-1][j]
            if p>=0:
                prev[i][j] = prev[i-1][p]
                vals[i][j] = op(vals[i-1][j], vals[i-1][p])
            else:
                prev[i][j] = p
                vals[i][j] = vals[i-1][j]
    return prev, vals

# k: 必要桁数を定める必要アリ
def cprev(u,i):
    """uからi個上の頂点を返す
    """
    vv = ninf
    for j in range(k):
        if i>>j&1:
            vv = op(vv, vals[j][u])
            u = prev[j][u]
    return u, vv

# k: 必要桁数を定める必要アリ
def lca(u,v):
    if depth[u]<depth[v]:
        v,val = cprev(v, depth[v]-depth[u])
    else:
        u,val = cprev(u, depth[u]-depth[v])
    if u==v:
        return u, val
    # 上のvalをそのまま↓に持ち越すので注意
    for i in range(k-1, -1, -1):
        if prev[i][u]!=prev[i][v]:
            val = op(vals[i][u], vals[i][v], val)
            u = prev[i][u]
            v = prev[i][v]
    return prev[0][u], op(val, vals[0][u], vals[0][v]) # このあたり注意

depth, ps = cdepth(ns,0)
k = 0
n = len(ps)
while pow(2,k)<n:
    k += 1
###
"""このあたりを書き換える
vs: 各ノードについての値
"""
def op(*args):
    return sum(args)
ninf = 0
###

prev,vals = double(ps,vs)
q = int(input())
ans = []
for i in range(q):
    x,y,z = map(lambda i: int(i), input().split())
    l, v1 = lca(x,y)
    l2, v2 = lca(y,z)
    l3, v3 = lca(x,z)
    res = (v1+v2+v3)//2
    ans.append(res)
write("\n".join(map(str, ans)))
0