时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Your town has been hit by an enormous amount of snow this winter. The town council has decided to buy a snow plow to clear the roads.
Problem specification
The town has n intersections, numbered 1 through n. These are all connected together by a network of n − 1 bidirectional roads. (In other words, the road network is a tree.) All roads have the same length.
At the beginning of winter, there was no snow anywhere. During the winter the snow plow made q journeys. For each journey, we know the path the plow travelled and whether it was snowing during that journey.
During each journey the plow travelled along the only simple path from the origin to the destination of the journey. If it did snow, it always snowed during the entire journey, and it always snowed in the entire town, not just on the plow’s path. All snowfall during the entire winter happened during some of the plow’s journeys.
Whenever the plow travels through a road, two things happen in order:
- All snow is removed from that road.
- If it’s snowing, every road in the town (including the one just cleaned) gains 1 cm of snow.
The destination of one journey might not be equal to the starting point of the next one. In that case, the snow plow isn’t active in the meantime – it moves to the next starting point without changing the amount of snow on the roads.
For each journey, compute the total amount of snow the plow removed during that journey.
输入描述:
The first line containing the integers n and q (1 ≤n≤ 10 000 000; 1 ≤q≤ 25 000 000). The next n− 1 lines contain integers pi,qi (1 ≤pi,qi ≤n) meaning that intersections pi and qi are connected by a road. The i-th of the following q lines contains integers ai,bi,ci (1 ≤ai,bi ≤n; 0 ≤ci ≤ 1) describing the i-th journey of the snow plow: The journey started at intersection ai and ended at intersection bi. We have ci = 1 if it snowed during this journey, and ci = 0 if it did not.
In the easy subproblem H1 it is guaranteed that there is a road between intersections i and i+ 1 for every 1 ≤i<n. (The road network is a line.)
Because the size of h1.in is about 800 MB and the size of h2.in is about 1.2 GB, you cannot download them directly. Instead, we have provided small Python 2 programs h1gen.py and h2gen.py that will generate h1.in and h2.in when executed. Each generator should take under 10 minutes to run on average hardware. We recommend running them early – for example, starting them as you start working on your solution for this problem.
输出描述:
For each test case: For i= 1, …,q, let yi be the total amount of snow removed during journey i, and let zi be i⋅yi. Output one line with a single number: