HDU 5877 Weak Pair (线段树+离散化+DFS)

HDU 5877 Weak Pair (线段树+离散化+DFS)

题目链接:点我~~ 题意:给出一棵n个结点的树和一个数k, 每个节点上有权值ai, 问有多少个有序对(u,v)满足u是v的祖先, 且au*av≤k. 思路:从根开始dfs, 用线段树维护当前节点u到根的节点权值序列, 数据很大,需要离散化,然后就查询小于等于k/au的数的个数. 之后把au插入, 然后继续查找子节点,回溯的时候再删去该节点。其实就是查找每个节...
09月21日 214
  1. .01
  2. .02