Counting on a Tree
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
You are given an unrooted tree with N nodes, numbered from 1 to N. Each edge of the tree has a positive integer, associated with it. Your goal is to calculate the number of unordered pairs (S, T) of tree's nodes such that the greatest common divisor of all the integers associated with the edges of the path between S and T is equal to one. Of course, we consider only the pairs where S isn't equal to T.
You are also given Q queries, where the ith query is described by two integer Ai and Ci. In the ith query, the number associated with the Aith edge will be changed Ci. You also want to calculate the answer for the tree after each query.
There is only one test case in one test file.
The first line of input contains an integer N, denoting the number of nodes in the tree. The ith line of the next N−1 lines contains the description of ith edge, where the line has three space-separated integers X, Y and Z. It means that ith edge connect nodes X and Y, and the associated integer is Z. Then the next line contains an integer Q, denoting the number of queries. The ith line of the next Q lines has two space-separated integers Ai and Ci.
In the first line, print the answer for the initial tree. Then print the answer for the tree after each query. Here the answer means that the number of unordered pairs (S, T) of the nodes such that the greatest common divisor of all the integers associated with the edges of the path between S and T is equal to one.
Constraints and Subtasks
- 1 ≤ X, Y ≤ N, and X ≠ Y
- 1 ≤ Z ≤ 106
- 0 ≤ Q ≤ 100
- 1 ≤ Ai ≤ N − 1
- 1 ≤ Ci ≤ 106
- The graph given in the input denotes a tree
Subtask 1 (27 points)
- 1 ≤ N ≤ 103
Subtask 2 (73 points)
- 1 ≤ N ≤ 105
Input: 5 1 2 10 1 3 6 3 4 15 3 5 15 2 4 5 1 7 Output: 2 3 4
The below figure shows the initial graph and the graph after each query.
The initial tree. The sought pairs are (2, 4) and (2, 5). For example, in the path between nodes 2 and 4, there are three integers 10, 6, 15 associated edges, and GCD(10, 6, 15) = 1.
After query 1. The sought pairs are (1, 5), (2, 4) and (2, 5).
After query 2. The sought pairs are (1, 5), (2, 3), (2, 4) and (2, 5).
|Tags||hard, march15, mobius_function, union-find, xcwgf666|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.