550. Tree Queries Online
Time limit per test: 6
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
This problem is a little unusual — here you must implement an online algorithm for processing special queries. This means that your program can start reading a request only after it prints the response to the previous one. Note that this problem has standard input/output (i.e., from the keyboard and to the screen). After writing response to a request, be sure to use the stream flushing function. Otherwise you risk leaving part of your output in i/o buffer. For example, you must use the
fflush(stdout)
function in C++, call
System.out.flush()
in Java, and
flush(output)
in Pascal.
You are given a weighted undirected tree containing
n vertices. The vertices are indexed by integers from 1 to
n. A tree is a connected graph without cycles. Your task is to process
n1 requests for it. Each request means removing one of its edges. Of course, after the first request the tree is no longer a tree, but it becomes a forest (a set of trees).
After processing each request your program should output the weight of the removed edge
w_{i}. In addition, the requests change the weights of other edges. When you remove an edge, the connected component that contains it splits into two. In the smaller (by the number of vertices) of the two resulting components the weights of the edges are multiplied by the weight
w_{i} of the removed edge, and in the larger component the weight of the removed edge
w_{i} is added to the weight of each edge. If both components have equal number of vertices, you should assume that the smaller one is the one that contains the vertex with the smallest index among the vertices of these two components.
All arithmetic operations must be performed modulo 99990001. That is, you only operate with numbers from 0 to 99990000, and in any arithmetic operation the result is the remainder of dividing the operation outcome by 99990001.
Input
The input to this problem must be read from the standard input stream. The first input line contains an integer
n (2 ≤
n ≤ 2·10
^{5}) — the number of vertexes in the tree. The next
n1 lines contain descriptions of the edges of the tree, one description per line. Each description consists of three integers
x_{i},
y_{i},
w_{i} (1 ≤
x_{i},
y_{i} ≤
n;
x_{i} ≠
y_{i}; 0 ≤
w_{i} ≤ 99990000) — the indexes of vertexes connected by the
ith edge and the initial weight of the
ith edge. The last input line contains sequence
p_{1},
p_{2},...,
p_{n1} — the permutation of integers from 1 to
n1, where
p_{i} is the number of the removed edge. The edges are numbered from 1 to
n1 in the order they follow in the input.
Remember that you can only read the next element of permutation
p_{1},
p_{2},...,
p_{n1} after the response to the current query is printed. During the testing the system won't let you read the data unless you follow this rule.
Output
The output must be written to the standard output. Print
n1 lines, the
jth line must contain the weight of the removed edge during the
jth query. Flush the output after each printed line, i.e. each time after your program writes endofline.
Example(s)
sample input

sample output

4
1 2 3
2 3 4
3 4 5
1 2 3

3
7
15

sample input

sample output

4
1 2 3
2 3 4
3 4 5
2 1 3

4
12
9
