結果

問題 No.1212 Second Path
ユーザー lam6er
提出日時 2025-03-31 17:47:35
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,021 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 152,536 KB
最終ジャッジ日時 2025-03-31 17:49:07
合計ジャッジ時間 10,424 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from collections import deque
sys.setrecursionlimit(1 << 25)
input = sys.stdin.readline

def main():
    import sys
    n = int(sys.stdin.readline())
    edges = [[] for _ in range(n + 1)]  # 1-based
    for _ in range(n - 1):
        u, v, w = map(int, sys.stdin.readline().split())
        edges[u].append((v, w))
        edges[v].append((u, w))
    
    LOG = 20
    parent = [[-1] * (n + 1) for _ in range(LOG)]
    depth = [0] * (n + 1)
    dist = [0] * (n + 1)  # distance from root to node
    
    root = 1
    stack = [(root, -1, 0, 0)]
    while stack:
        node, par, d, di = stack.pop()
        parent[0][node] = par
        depth[node] = d
        dist[node] = di
        for neighbor, w in edges[node]:
            if neighbor != par:
                stack.append((neighbor, node, d + 1, di + w))
    
    # Build binary lifting table
    for k in range(1, LOG):
        for v in range(1, n + 1):
            if parent[k - 1][v] != -1:
                parent[k][v] = parent[k - 1][parent[k - 1][v]]
    
    def lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        # Bring u to the same depth as v
        for k in range(LOG - 1, -1, -1):
            if depth[u] - (1 << k) >= depth[v]:
                u = parent[k][u]
        if u == v:
            return u
        for k in range(LOG - 1, -1, -1):
            if parent[k][u] != -1 and parent[k][u] != parent[k][v]:
                u = parent[k][u]
                v = parent[k][v]
        return parent[0][u]
    
    def get_path(u, lca_node):
        path = []
        while u != lca_node:
            path.append(u)
            u = parent[0][u]
        path.append(lca_node)
        return path
    
    q = int(sys.stdin.readline())
    for _ in range(q):
        x, y = map(int, sys.stdin.readline().split())
        if x == y:
            print(-1)
            continue
        l = lca(x, y)
        path_x = get_path(x, l)
        path_y = get_path(y, l)
        path = path_x + path_y[-2::-1]  # Combine x to lca and y to lca (reversed)
        if len(path) == 1:
            print(-1)
            continue
        # Build edge set
        edge_set = set()
        for i in range(len(path) - 1):
            u = path[i]
            v = path[i + 1]
            if u > v:
                u, v = v, u
            edge_set.add((u, v))
        min_candidate = float('inf')
        # Sort the edges for each node to optimize checking
        sorted_edges = [[] for _ in range(n + 1)]
        for u in range(n + 1):
            sorted_edges[u] = sorted(edges[u], key=lambda x: x[1])
        for u in path:
            next_idx = path.index(u) + 1 if u != path[-1] else -1
            prev_idx = path.index(u) - 1
            neighbors_in_path = set()
            if prev_idx >= 0:
                prev_node = path[prev_idx]
                neighbors_in_path.add(prev_node)
            if next_idx < len(path) and next_idx >= 0:
                next_node = path[next_idx]
                neighbors_in_path.add(next_node)
            # Check each adjacent edge of u
            for v, w in sorted_edges[u]:
                # Check if (u, v) is in edge_set
                a, b = (u, v) if u < v else (v, u)
                if (a, b) not in edge_set:
                    candidate = 2 * w
                    if candidate < min_candidate:
                        min_candidate = candidate
                    break  # Since sorted, the first one is minimal
                # Check if v is not in the neighbors_in_path
                # Because sometimes, the edge is part of the path but not in the edge_set (unlikely)
                # but wait, no, edge_set contains all edges in the path, so if (a, b) is in edge_set, it's part of the path
            # Now, after checking all adjacent edges
        if min_candidate != float('inf'):
            s = dist[x] + dist[y] - 2 * dist[l]
            print(s + min_candidate)
        else:
            print(-1)

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