GCD on a tree
Tag(s):

## Depth-first search, Inclusion Exclusion, Inclusion exclusion principle, Mathematics, 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: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## 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 > Number Theory