package main import ( "bufio" "container/heap" "fmt" "math" "os" "strconv" ) func configure(scanner *bufio.Scanner) { scanner.Split(bufio.ScanWords) scanner.Buffer(make([]byte, 1000005), 1000005) } func getNextString(scanner *bufio.Scanner) string { scanned := scanner.Scan() if !scanned { panic("scan failed") } return scanner.Text() } func getNextInt(scanner *bufio.Scanner) int { i, _ := strconv.Atoi(getNextString(scanner)) return i } func getNextInt64(scanner *bufio.Scanner) int64 { i, _ := strconv.ParseInt(getNextString(scanner), 10, 64) return i } func getNextFloat64(scanner *bufio.Scanner) float64 { i, _ := strconv.ParseFloat(getNextString(scanner), 64) return i } func main() { fp := os.Stdin wfp := os.Stdout extra := 0 if os.Getenv("I") == "IronMan" { fp, _ = os.Open(os.Getenv("END_GAME")) extra = 100 } scanner := bufio.NewScanner(fp) configure(scanner) writer := bufio.NewWriter(wfp) defer func() { r := recover() if r != nil { fmt.Fprintln(writer, r) } writer.Flush() }() solve(scanner, writer) for i := 0; i < extra; i++ { fmt.Fprintln(writer, "-----------------------------------") solve(scanner, writer) } } func solve(scanner *bufio.Scanner, writer *bufio.Writer) { n := getNextInt(scanner) g := newGraph(n) for i := 0; i < n-1; i++ { a := getNextInt(scanner) - 1 b := getNextInt(scanner) - 1 c := getNextInt(scanner) g.AppendEdge(a, b, i, c) g.AppendEdge(b, a, i, c) } for i := 0; i < n; i++ { g.v[i].c = math.MaxInt32 } dd := &daikes{} heap.Push(dd, &daike{i: 0, c: 0}) for dd.Len() > 0 { p := heap.Pop(dd).(*daike) if g.v[p.i].c <= p.c { continue } g.v[p.i].c = p.c for _, e := range g.e[p.i] { heap.Push(dd, &daike{i: e.to, c: p.c + e.c}) } } g.Dfs(0, -1, 0) g.Doubling() q := getNextInt(scanner) for q > 0 { q-- s := getNextInt(scanner) - 1 t := getNextInt(scanner) - 1 lca := g.Lca(s, t) fmt.Fprintln(writer, g.v[s].c+g.v[t].c-g.v[lca].c<<1) } } type daike struct { i int c int } type daikes []*daike func (h daikes) Len() int { return len(h) } func (h daikes) Less(i, j int) bool { return h[i].c < h[j].c } func (h daikes) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *daikes) Push(x interface{}) { *h = append(*h, x.(*daike)) } func (h *daikes) Pop() interface{} { old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x } type vertex struct { depth int parent [32]int c int } type edge struct { to, id int c int } type graph struct { v []vertex e [][]edge } func newGraph(n int) graph { return graph{ v: make([]vertex, n), e: make([][]edge, n), } } func (g *graph) AppendEdge(from, to, id int, c int) { g.e[from] = append(g.e[from], edge{ to: to, id: id, c: c, }) } func (g *graph) Dfs(i, p, depth int) { g.v[i].parent[0] = p g.v[i].depth = depth for _, e := range g.e[i] { if e.to == p { continue } g.Dfs(e.to, i, depth+1) } } func (g *graph) Doubling() { for d := 1; d < 32; d++ { for i := 0; i < len(g.v); i++ { if g.v[i].parent[d-1] == -1 { g.v[i].parent[d] = -1 continue } g.v[i].parent[d] = g.v[g.v[i].parent[d-1]].parent[d-1] } } } func (g *graph) Lca(u, v int) int { if g.v[u].depth > g.v[v].depth { u, v = v, u } d := g.v[v].depth - g.v[u].depth for i := 0; i < 32; i++ { if d>>uint(i)&1 == 1 { v = g.v[v].parent[i] } } if v == u { return v } for i := 31; i >= 0; i-- { if g.v[v].parent[i] == g.v[u].parent[i] { continue } v = g.v[v].parent[i] u = g.v[u].parent[i] } return g.v[v].parent[0] }