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 i^{th} query is described by two integer A_{i} and C_{i}. In the i^{th} query, the number associated with the A_{i}^{th} edge will be changed C_{i}. You also want to calculate the answer for the tree after each query.
Input
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 i^{th} line of the next N−1 lines contains the description of i^{th} edge, where the line has three spaceseparated integers X, Y and Z. It means that i^{th} 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 i^{th} line of the next Q lines has two spaceseparated integers A_{i} and C_{i}.
Output
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 ≤ 10^{6}
 0 ≤ Q ≤ 100
 1 ≤ A_{i} ≤ N − 1
 1 ≤ C_{i} ≤ 10^{6}
 The graph given in the input denotes a tree
Subtask 1 (27 points)
 1 ≤ N ≤ 10^{3}
Subtask 2 (73 points)
 1 ≤ N ≤ 10^{5}
Example
Input: 5 1 2 10 1 3 6 3 4 15 3 5 15 2 4 5 1 7 Output: 2 3 4
Explanation
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).
Author:  xcwgf666 
Tester:  laycurse 
Editorial  http://discuss.codechef.com/problems/TREECNT2 
Tags  hard, march15, mobius_function, unionfind, xcwgf666 
Date Added:  9022015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions