#P5480. 路径的条数

    ID: 4483 传统题 3000ms 512MiB 尝试: 71 已通过: 12 难度: 8 上传者: 标签>CF2500提高+/省选-补集计数倍数枚举子树转区间树上倍增扫描线普通线段树

路径的条数

Description

给一棵n个点的有标号无根树,你需要找到满足条件的路径u−v的条数。

我们称路径u-v满足条件当且仅当u,v且路径u-v上不存在点对(a,b),a,b满足gcd(a,b)=a。

注意:路径u−v和v−u是同一条路径。

Format

Input

第一行一个整数n,n<=10^5 接下来n−1行,每行两个用空格隔开的整数a,b,表示边(a,b) 只有路径 2 − 3 和 3 − 4 满足条件

Output

一行一个整数,代表要求的答案。

Samples

4 
3 1
3 2
3 4
2