All Tracks Math Combinatorics Inclusion-Exclusion Problem

GCD on a tree
/

Depth-first search, Inclusion Exclusion, Inclusion exclusion principle, Mathematics, 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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Уведомления
View All Notifications

?