[AdditionalFile5686.zip](file://AdditionalFile5686.zip?type=additional_file)

#5686. 「PA 2026」Zbugujemy dziś bałwana?

标签: 传统 | 时间限制: 10000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2026 Runda 4 Zbugujemy dziś bałwana?

昨晚，Bajtogóra 下了入冬以来的第一场雪。作为市长，你决定庆祝这一时刻，并借清理道路的机会堆一个巨大的雪人。城市中有 $n$ 个交叉口，编号从 $1$ 到 $n$，由 $n-1$ 条双向街道连接（死胡同的尽头也是交叉口）。城市间的道路网呈树状结构。对于每条街道，我们知道它连接哪两个交叉口及其长度。雪均匀地覆盖在所有地方，即在长度为 $w$ 的街道上覆盖了 $w$ 单位的雪。

雪人由三个雪球组成，每个雪球都是通过沿着某条特定路径滚动整个路径上的所有雪形成的。路径可以从交叉口开始，也可以从街道的任意点开始。随后路径经过一系列不同的街道和交叉口，最后可以在街道的任意点或交叉口结束。滚好的雪球将由直升机运往雪人建造地点。

任何两条路径不能经过同一点，否则会导致雪球沾上泥巴。更准确地说，地图上的任何一点（特别是交叉口）不能是两条不同路径的内部点。我们假设在滚雪球的起点和终点处不收集雪，因此在同一点可以有不止一条路径开始或结束（路径也可以在另一条路径的内部点开始或结束）。

你还没有决定雪人的各个雪球具体会有多大，因此还不清楚需要多少雪。你正在考虑 $q$ 个潜在的设计方案；每个方案由三个整数 $a_{i} \leq b_{i} \leq c_{i}$ 描述，代表各个雪球的大小（从雪人顶部到底部）。

对于每个方案，请确定是否能按上述方式构建雪人。

输入格式

第一行输入包含两个整数 $n$ 和 $q$ $(2 \leq n \leq 200000, 1 \leq q \leq 200000)$，分别表示 Bajtogóra 的交叉口数量和雪人设计方案的数量。

接下来的 $n-1$ 行包含街道的描述；每行由三个整数 $u_{i}, v_{i}$ 和 $w_{i}$ $(1 \leq u_{i}, v_{i} \leq n; 1 \leq w_{i} \leq 10^{9})$ 组成，描述连接交叉口 $u_{i}$ 和 $v_{i}$ 的街道，该街道上有 $w_{i}$ 单位的雪。

接下来的 $q$ 行包含雪人设计方案。每行由三个整数 $a_{i}, b_{i}$ 和 $c_{i}$ $(1 \leq a_{i} \leq b_{i} \leq c_{i} \leq 10^{15})$ 组成，描述第 $i$ 个设计方案中各个雪球的大小。

输出格式

输出 $q$ 行；如果可以根据第 $i$ 个方案构建雪人第 $i$ 行应输出 TAK，否则输出 NIE。

样例

输入

9 11
1 2 25
2 3 2
2 4 5
1 5 5
1 6 6
1 7 1
7 8 2
7 9 2
57 57 57
12 12 12
6 8 30
1 8 31
7 7 25
10 15 15
5 11 27
5 7 31
4 5 36
12 12 13
7 7 26

输出

NIE
TAK
TAK
NIE
TAK
TAK
TAK
TAK
TAK
NIE
NIE

• 第一个方案（雪球为 $57, 57, 57$）无法构建。城市里的雪不足以支撑这么大的雪人。
• 构建 $12, 12, 12$ 的雪人可以使用以下路径：
  • $6-1-2$（部分路段），收集 $6+6=12$ 单位雪。
  • $4-2-1$（部分路段），收集 $5+7=12$ 单位雪。
  • 在 $1-2$ 号街道的剩余部分还剩下 $25-6-7=12$ 单位雪，足以构建第三个雪球。
• 构建 $6, 8, 30$ 的雪人可以使用以下路径：
  • $1-6$，收集 $6$ 单位雪。
  • $5-1-7-8$，收集 $5+1+2=8$ 单位雪。
  • $1-2-4$，收集 $25+5=30$ 单位雪。 请注意，交叉口 $1$ 仅位于一条路径内部，因此没有雪球会沾上泥巴。
• 构建 $1, 8, 31$ 的雪人无法使用以下路径：
  • $2-3$，
  • $5-1-6$，
  • $7-1-2-4$。 尽管雪量充足，但这三条路径都使用了交叉口 $1$ 的雪，这会导致其中一个雪球沾上泥巴。
• 构建 $7, 7, 25$ 的雪人可以使用以下路径：
  • $3-2-4$，收集 $2+5=7$ 单位雪。
  • $6-1-7$，收集 $6+1=7$ 单位雪。
  • $1-2$，收集 $25$ 单位雪。

数据范围与提示

子任务按 $n$ 的取值范围排序。在第 $1$ 个子任务中，$w_{i}$ 的总和不超过 $60$。在第 $1, 3, 5$ 个子任务中，满足额外条件 $q \leq 200$。