NC212613. APartyforYouStarted
描述
Welcome to the grand party for CJLUACMer, we are glad about your arrival. Before starting, please remind that the difficulty of all the problems is absolutely not relevant to its order of permutation, so please consider the order of accomplishment by yourself. Now let us get started!
CJLUACMer comes from N factions. Some factions with the majority of people, based on broad range fields, such as Mathematics, and others may be more specific, such as Geometry, Algebra. Moreover, it contains complex relationships beyond different types of factions. For example, let faction 1(Geometry) belongs to faction 2(Mathematics) if there are two people from faction 1 and one person from faction 2 initially. We can say there are two people belongs to faction 1 or three people belongs to faction 2. People attending parties like to ask if somebody is present, so when someone from a certain faction comes, he(or she) will ask the security guard GYQ how many people have come from another particular faction, maybe wide range or just minority.
Generally, every moment there will be x people who belong to the faction u arrive at the party, and they will ask how many people had come from the faction v. The security guard GYQ had to run in to check the number of people every time, so he was so busy and sweaty.
Now given that CJLUACMer has N factions in total and M groups of people who come to the party once at a time. And given an array a, the index
represents the parent faction of the i-th faction, it's guaranteed that each specific faction belongs to only one superior faction(which means just a level higher), and there is exactly one 0 in the array, which indicates the whole CJLUACM association and this faction is the largest. After that, there will be M queries within the format of `u x v`, whose meaning is as described above. Could you help the security guard GYQ answer every query?
CJLUACMer comes from N factions. Some factions with the majority of people, based on broad range fields, such as Mathematics, and others may be more specific, such as Geometry, Algebra. Moreover, it contains complex relationships beyond different types of factions. For example, let faction 1(Geometry) belongs to faction 2(Mathematics) if there are two people from faction 1 and one person from faction 2 initially. We can say there are two people belongs to faction 1 or three people belongs to faction 2. People attending parties like to ask if somebody is present, so when someone from a certain faction comes, he(or she) will ask the security guard GYQ how many people have come from another particular faction, maybe wide range or just minority.
Generally, every moment there will be x people who belong to the faction u arrive at the party, and they will ask how many people had come from the faction v. The security guard GYQ had to run in to check the number of people every time, so he was so busy and sweaty.
Now given that CJLUACMer has N factions in total and M groups of people who come to the party once at a time. And given an array a, the index
输入描述
Each input file only contains one test case.
The first line contains two integers N and M (1 ≤ N ≤ 2 ×, 1 ≤ M ≤
), indicating the number of the factions and the queries.
The second line contains N integers,
,……,
(1 ≤
Then followed M lines, each line contains three integers u, x, v (1 ≤ u, v ≤ N, 1 ≤ x ≤), indicating there are x people who belong to the faction u arrive at the party, and they asked how many people had come from the faction v.
输出描述
Print M lines, each line contains an integer indicating the answer of the security guard GYQ in order.
示例1
输入:
4 5 0 1 1 2 1 2 2 2 1 2 4 1 2 3 1 3 3 1 4
输出:
0 2 3 2 4