#P16274. [2022Acm Hongkong]Smaller LCA更小的 LCA

    ID: 15485 传统题 4000ms 512MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-补集计数暴力枚举换根 DP离线查询树上差分树状数组子树转区间LCA树上倍增

[2022Acm Hongkong]Smaller LCA更小的 LCA

题目描述

Grammy 有一棵包含 nn 个顶点的树,顶点编号为 1,2,…,n1,2,\ldots,n。

对于每一个顶点 rr,分别将这棵树以 rr 为根。

Grammy 想知道:有多少个无序点对 (x,y)(x,y),使得 xx 和 yy 的最近公共祖先为 zz,并满足

z≤x⋅y.z\le x\cdot y.

这里的无序点对允许两个端点相同,即可以认为需要统计所有满足

1≤x≤y≤n1\le x\le y\le n

的点对。

请对每一个可能的根分别计算答案。

输入格式

第一行包含一个整数 nn,表示树的顶点数。

1≤n≤300000.1\le n\le 300000.

接下来 n−1n-1 行,每行包含两个整数 ui,viu_i,v_i,表示树中存在一条连接顶点 uiu_i 和顶点 viv_i 的边。

1≤ui,vi≤n.1\le u_i,v_i\le n.

输出格式

输出 nn 行。

第 ii 行输出一个整数,表示以顶点 ii 为根时,满足条件的无序点对数量。

样例

输入:
5
1 2
4 2
2 5
3 5

输出:
15
15
15
15
14