結果

問題 No.1212 Second Path
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:40:47
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,790 bytes
コンパイル時間 312 ms
コンパイル使用メモリ 81,852 KB
実行使用メモリ 313,344 KB
最終ジャッジ日時 2025-06-12 19:41:00
合計ジャッジ時間 12,453 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    adj = [[] for _ in range(N+1)]
    edges = {}
    for _ in range(N-1):
        u = int(data[idx])
        v = int(data[idx+1])
        w = int(data[idx+2])
        idx +=3
        adj[u].append((v, w))
        adj[v].append((u, w))
        if u > v:
            u, v = v, u
        edges[(u, v)] = w

    Q = int(data[idx])
    idx +=1
    queries = []
    for _ in range(Q):
        x = int(data[idx])
        y = int(data[idx+1])
        queries.append((x, y))
        idx +=2

    parent = [0]*(N+1)
    depth = [0]*(N+1)
    visited = [False]*(N+1)
    q = deque()
    q.append(1)
    visited[1] = True
    while q:
        u = q.popleft()
        for v, w in adj[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                depth[v] = depth[u] +1
                q.append(v)

    def lca(u, v):
        while depth[u] > depth[v]:
            u = parent[u]
        while depth[v] > depth[u]:
            v = parent[v]
        while u != v:
            u = parent[u]
            v = parent[v]
        return u

    def get_path(u, v):
        res = []
        while u != v:
            if depth[u] >= depth[v]:
                res.append(u)
                u = parent[u]
            else:
                res.append(v)
                v = parent[v]
        res.append(u)
        return res[::-1]

    for x, y in queries:
        a = x
        b = y
        ancestor = lca(a, b)
        path_a = []
        u = a
        while u != ancestor:
            path_a.append(u)
            u = parent[u]
        path_a.append(ancestor)
        path_b = []
        u = b
        while u != ancestor:
            path_b.append(u)
            u = parent[u]
        path = path_a + path_b[::-1]

        path_set = set()
        for i in range(len(path)-1):
            u = path[i]
            v = path[i+1]
            if u > v:
                u, v = v, u
            path_set.add((u, v))

        min_w = None
        for u in path:
            for v, w in adj[u]:
                if u < v:
                    e = (u, v)
                else:
                    e = (v, u)
                if e not in path_set:
                    if min_w is None or w < min_w:
                        min_w = w

        if min_w is not None:
            S = 0
            for i in range(len(path)-1):
                u = path[i]
                v = path[i+1]
                if u > v:
                    u, v = v, u
                S += edges[(u, v)]
            print(S + 2 * min_w)
        else:
            print(-1)

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