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, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

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

?