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

## This Problem was Asked in

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

?