1. 首页
  2. DFS, 线段树

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

题目链接:点我~~

题意:给出一棵n个结点的树和一个数k, 每个节点上有权值ai, 问有多少个有序对(u,v)满足uv的祖先, 且au*avk.

思路:从根开始dfs, 用线段树维护当前节点u到根的节点权值序列, 数据很大,需要离散化,然后就查询小于等于k/au的数的个数. 之后把au插入, 然后继续查找子节点,回溯的时候再删去该节点。其实就是查找每个节点有多少个父节点满足条件,就是一遍dfs的过程。

 

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
  • 版权声明:本文基于《知识共享署名-相同方式共享 3.0 中国大陆许可协议》发布,转载请遵循本协议
  • 文章链接:http://www.carlstedt.cn/archives/1152 (转载时请注明本文出处及文章链接)
上一篇:
:下一篇

1 条评论

gravatar

  1. frpp双壁波纹管 2016-09-22 unknowunknow

    技术型站长,支持下。欢迎回访

    回复 沙发
  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40