GCD on a tree
Tag(s):

## DFS, Inclusion Exclusion, Math, Medium, Mobius Function

Problem
Editorial
Analytics

You are given a tree with $n$ nodes. The nodes are numbered from $1$ to $n$. Let us define the gcd of a path as the greatest common divisor of all values of the nodes in the path. Let $F(g)$ denote the number of simple paths on the tree whose gcd is $g$. Formally, $F(g)$ equals the number of sequences $p_1,p_2, \cdots , p_k$, such that $p_i$ and $p_{i+1}$ are connected by an edge for all $i < k$, and $p_i \neq p_j$ for $i \neq j$, and $gcd(p_1,p_2,\cdots p_k) = g$.

Find the values of $F(g)$ for all $1 \leq g \leq n$

Input
The first line contains $n$, the number of nodes in the tree.
Each of the next $n-1$ lines contain 2 integers $u,v$, denoting node $u$, and node $v$ are connected by an edge.

Output
Print a single line containing $n$ integers. The $i^{\text{th}}$ integer equals $F(i)$.

Constraints
$1 \le n \le 10^6$

SAMPLE INPUT
4
1 2
2 3
2 4
SAMPLE OUTPUT
11 3 1 1
Explanation

The path from $2$ to $4$, and the path from $4$ to $2$, has gcd value 2. All other paths with more than 1 nodes have gcd 1. The path $i$ to $i$ has gcd $i$

Time Limit: 6.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

November Circuits

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Math > Number Theory
• Math > Basic Math
• Math > Number Theory