結果

問題 No.898 tri-βutree
ユーザー shotoyooshotoyoo
提出日時 2021-07-17 18:00:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,481 ms / 4,000 ms
コード長 3,128 bytes
コンパイル時間 657 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 173,024 KB
最終ジャッジ日時 2024-07-07 05:19:24
合計ジャッジ時間 25,200 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 682 ms
173,024 KB
testcase_01 AC 34 ms
53,632 KB
testcase_02 AC 49 ms
65,364 KB
testcase_03 AC 43 ms
63,036 KB
testcase_04 AC 44 ms
62,744 KB
testcase_05 AC 45 ms
63,820 KB
testcase_06 AC 44 ms
62,944 KB
testcase_07 AC 1,447 ms
158,972 KB
testcase_08 AC 1,480 ms
159,496 KB
testcase_09 AC 1,417 ms
158,080 KB
testcase_10 AC 1,420 ms
158,980 KB
testcase_11 AC 1,416 ms
158,932 KB
testcase_12 AC 1,481 ms
159,016 KB
testcase_13 AC 1,409 ms
159,448 KB
testcase_14 AC 1,439 ms
158,348 KB
testcase_15 AC 1,413 ms
159,696 KB
testcase_16 AC 1,416 ms
158,756 KB
testcase_17 AC 1,440 ms
159,716 KB
testcase_18 AC 1,447 ms
158,696 KB
testcase_19 AC 1,461 ms
159,472 KB
testcase_20 AC 1,413 ms
158,444 KB
testcase_21 AC 1,440 ms
160,628 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