#P6785. [2019福建夏令营]树

    ID: 6605 传统题 2000ms 1024MiB 尝试: 5 已通过: 1 难度: 7 上传者: 标签>难度分类提高+/省选-树算法点分治点分祖先维护距离数据结构普通线段树排序与序列处理二分查找CF2200

[2019福建夏令营]树

树(tree)

题目描述

给定一棵有 nn 个节点的带权树,节点编号为 11 到 nn。

有 mm 次询问。每次给定 l,r,xl,r,x,求从节点 xx 到编号属于区间 [l,r][l,r] 的节点的最短距离,即

min⁡l≤v≤rdist⁡(x,v).\min_{l\le v\le r}\operatorname{dist}(x,v).

两点的距离为连接它们的唯一路径上所有边长之和。如果 l≤x≤rl\le x\le r,则答案为 00。

输入格式

第一行一个正整数 nn。

接下来 n−1n-1 行,每行三个正整数 u,v,wu,v,w,表示节点 uu 与节点 vv 之间有一条长度为 ww 的边。

接下来一行一个正整数 mm。

接下来 mm 行,每行三个正整数 l,r,xl,r,x,描述一次询问,其中 1≤l≤r≤n1\le l\le r\le n,1≤x≤n1\le x\le n。

输出格式

输出 mm 行,每行一个整数,表示对应询问的答案。

样例输入

3
1 2 1
1 3 1
3
2 3 1
2 3 2
3 3 2

样例输出

1
0
2

数据范围

  • 对于 30%30\% 的数据,n,m≤1000n,m\le1000。
  • 另有 20%20\% 的数据,节点 22 到 nn 均与节点 11 有边相连。
  • 另有 10%10\% 的数据,对所有 1≤i<n1\le i<n,节点 ii 与节点 i+1i+1 有边相连。
  • 对于所有数据,n,m≤105n,m\le10^5,任意两点之间的距离不超过 10910^9。