这个题本质上考的就是大家的计算思维。这个通常在ACM/OI中有考察。而在部分好一点的大学中,会开一门课《具体数学》,在学《求和式》一章时,里面也会有涉及到这种思想。
一个朴素的想法是:对每个节点求f(i) :对于每个i , 我们统计出i的子树集合。接下来枚举每个子孙节点,判断是否j是i的因子,是的话f(i)+=1
仙舟罗浮上有一棵建木,据说服下建木生成的神实就可以得到“无尽形寿“的身体,蜕变为长生种。米小游是短生种,因此她很想找到神实。 建木是一棵有n个节点的有根树,节点编号为1~n,根节点为x
对于编号为i的节点,f(i)表示以i为根的子树中,节点编号是i的因子的节点个数。
建木上神实的总数就是∑inf(i),米小游想知道建木上神实的总数是多少。
第一行包含两个整数n,x(1≤x,n≤105),表示树的节点个数,根节点编号
接下来n−1行,每行两个数u,v(1≤u,v≤n),表示一条u到v的树边。数据保证一定是一棵树。
输出包含一个整数,表示建木上神实的总数。
输入
4 4
1 2
4 3
2 4
输出
7
说明
以节点4为根的子树的节点有[1,2,3,4],其中[1,2,4]是4的因子,f(4)=3.
以节点2为根的子树的节点有[1,2],其中[1,2]是2的因子,f(2)= 2。
以节点1为根的子树的节点有[1],其中|1]是1的因子,f(1)= 1。
以节点3为根的子树的节点有[3],其中[3]是3的因子,f(3)= 1。
总和为1+2+1+3=7