All Tracks Math Combinatorics Inclusion-Exclusion Problem

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...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

November Circuits

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications