5877专题

hdu 5877 - Weak Pair (2016大连网络赛) 离散化 + 树状数组

题意:给出一棵树,n个节点,每个节点有一个权值,输入一个k,问有多少对点,满足点的权值乘积小于等于k,并且其中一个点是另一个点的祖先节点。 对于每一个节点,如果这个节点的权值为a,那么找到子节点所有的权值小于等于k/a的节点数量就是满足条件的对数(a=0时就是所有子节点都满足条件)。通过树状数组对统计做一个时间优化,用dfs处理,当处理到一个节点的时候,先减去树状数组中已经有的满足条件的数量,然