Maurice Tutor

(5)

$15/per page/Negotiable

About Maurice Tutor

Levels Tought:
Elementary,Middle School,High School,College,University,PHD

Expertise:
Algebra,Applied Sciences See all
Algebra,Applied Sciences,Biology,Calculus,Chemistry,Economics,English,Essay writing,Geography,Geology,Health & Medical,Physics,Science Hide all
Teaching Since: May 2017
Last Sign in: 399 Weeks Ago, 1 Day Ago
Questions Answered: 66690
Tutorials Posted: 66688

Education

  • MCS,PHD
    Argosy University/ Phoniex University/
    Nov-2005 - Oct-2011

Experience

  • Professor
    Phoniex University
    Oct-2001 - Nov-2016

Category > Computer Science Posted 17 Sep 2017 My Price 9.00

unrooted tree

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.

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 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.

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 = 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

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).

Answers

Maurice Tutor
(5)
Status NEW Posted 17 Sep 2017 12:09 PM My Price 9.00

Hel-----------lo -----------Sir-----------/Ma-----------dam-----------Tha-----------nk -----------You----------- fo-----------r u-----------sin-----------g o-----------ur -----------web-----------sit-----------e a-----------nd -----------and----------- ac-----------qui-----------sit-----------ion----------- of----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n.P-----------lea-----------se -----------pin-----------g m-----------e o-----------n c-----------hat----------- I -----------am -----------onl-----------ine----------- or----------- in-----------box----------- me----------- a -----------mes-----------sag-----------e I----------- wi-----------ll

Not Rated(0)