小机房有棵焕狗种的树，树上有 N 个节点，节点标号为 0 到 N-1 ，有两只虫子名叫飘狗和大吉狗，分居在两个不同的节点上。有一天，他们想爬到一个节点上去搞基，但是作为两只虫子，他们不想花费太多精力。已知从某个节点爬到其父亲节点要花费 c 的能量（从父亲节点爬到此节点也相同），他们想找出一条花费精力最短的路，以使得搞基的时候精力旺盛，他们找到你要你设计一个程序来找到这条路，要求你告诉他们最少需要花费多少精力。

假设有 N 个城镇，首都编号为 1 ，商人从首都出发，其他各城镇之间都有道路连接，任意两个城镇之间如果有直连道路，在他们之间行驶需要花费单位时间。该国公路网络发达，从首都出发能到达任意一个城镇，并且公路网络不会存在环，计算最短旅行时间。

给出一棵树，有 n 次查询最近公共祖先，输出所有查询所涉及到顶点的次数，未涉及则不输出。

树中有 n 个节点， n-1 条边，现查询节点 a 与节点 b 的最近公共祖先。