BobH的gal引擎

评测限制

内存限制 : 128MB

时间限制 : 1s

语言限制 : C/C++/Python/Java

题目背景

​ BobH 最近发现 吴骏驰 经常沉迷在一款名为 TinySnow 的国产 Galgame 里无法自拔，更令他感到生气的是国人制作的 Galgame 居然是用的岛国开发的 kirikiri 游戏引擎。

​ 这让他非常不爽，于是他希望自己开发一款中国的 Galgame 引擎。你很有幸也参与到了这个引擎的开发中来，并被要求负责制作其中一个重要的模块 —— 游戏选项分支跳转模块。

题目描述

​ 由于 galgame 涉及到很多玩家选择选项的分支，不同的分支会对应不同的结果，有一些是good end，而有一些是bad end。当玩家玩到bad end的时候，就会选择跳回之前的选择环节而选择另一个选项，从而得到更好的结果。

​ 整个游戏的所有选项对应的结果可以抽象成一棵树的结构，你的任务是 给定你一棵以1号节点为根树，两个节点之间有一条距离为$w$的边，每次询问你两个节点 $u,v$，你需要回答这两个节点最近一次的分叉点是哪个 以及 从$u$跳到$v$最短需要走的路程是多长。

​ 换一个更通俗易懂的描述，给你一棵以1号节点为根树，并告诉你两个节点间的距离，求树上两个节点 $u,v$ 的最短路并求出最短路径上深度最浅的一个点。

输入格式

​ 由于你是参与的BobH的团队编程，BobH对模块的规范要求很严格，他会这样调用你的模块：

​ 第一行输入如下格式 BobHEneg.Tree.init(n,q) 其中 $n$ 代表整棵树的节点数， $q$ 代表整个引擎会询问你的次数

​ 接下来 $n-1$ 行，每行格式如下 BobHEneg.Tree.insert(u,v,w) 代表 节点 $u$ 和节点 $v$ 之间有一条距离为 $w$ 的边

​ 接下来 $q$ 行，每行格式如下 BobHEneg.Tree.GetInfo(u,v) 表示询问节点 $u,v$ 相关信息

输出格式

​ 输出 $q$ 行，每行格式需按照这样的格式 {status:"ok",res:{top:[A],dis:[B]}} 其中 [A] 表示你求出来的路径上深度最浅的那个点，[B] 表示 $u,v$ 间的最短路径距离。

样例输入1

BobHEneg.Tree.init(12,4)
BobHEneg.Tree.insert(1,2,1)
BobHEneg.Tree.insert(2,4,3)
BobHEneg.Tree.insert(4,11,2)
BobHEneg.Tree.insert(2,5,4)
BobHEneg.Tree.insert(5,6,1)
BobHEneg.Tree.insert(5,7,3)
BobHEneg.Tree.insert(7,12,1)
BobHEneg.Tree.insert(5,8,2)
BobHEneg.Tree.insert(1,3,1)
BobHEneg.Tree.insert(3,9,3)
BobHEneg.Tree.insert(3,10,5)
BobHEneg.Tree.GetInfo(6,8)
BobHEneg.Tree.GetInfo(6,12)
BobHEneg.Tree.GetInfo(10,4)
BobHEneg.Tree.GetInfo(11,6)

样例输出1

{status:"ok",res:{top:5,dis:3}}
{status:"ok",res:{top:5,dis:5}}
{status:"ok",res:{top:1,dis:10}}
{status:"ok",res:{top:2,dis:10}}

样例解释1

​ 如下图

​

数据范围

​ 对于 $30\%$ 的数据，$n ≤ 10 ，q ≤ 10$

​ 对于 $70\%$的数据，$n ≤ 10000，q ≤ 10000$

​ 对于 $100\%$的数据，$n ≤ 500000，q ≤ 500000$