550. Tree Queries Online
Time limit per test: 6
Memory limit: 262144
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
function in C++, call
in Java, and
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 n
-1 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 wi
. 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 wi
of the removed edge, and in the larger component the weight of the removed edge wi
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.
The input to this problem must be read from the standard input stream. The first input line contains an integer n
(2 ≤ n
) — the number of vertexes in the tree. The next n
-1 lines contain descriptions of the edges of the tree, one description per line. Each description consists of three integers xi
(1 ≤ xi
; 0 ≤ wi
≤ 99990000) — the indexes of vertexes connected by the i
-th edge and the initial weight of the i
-th edge. The last input line contains sequence p1
— the permutation of integers from 1 to n
-1, where pi
is the number of the removed edge. The edges are numbered from 1 to n
-1 in the order they follow in the input.
Remember that you can only read the next element of permutation p1
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.
The output must be written to the standard output. Print n
-1 lines, the j
-th line must contain the weight of the removed edge during the j
-th query. Flush the output after each printed line, i.e. each time after your program writes end-of-line.
1 2 3
2 3 4
3 4 5
1 2 3
1 2 3
2 3 4
3 4 5
2 1 3