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日 1,834
HDU 5723 Abandoned country (最小生成树+dfs)

HDU 5723 Abandoned country (最小生成树+dfs)

题目链接:点我~~ 题意:~~ 思路:首先注意到任意两条边的边权是不一样的,由此得知最小生成树是唯一的,最小生成树既然 是唯一的,那么期望其实也就是唯一的,不存在什么最小期望。求完最小生成树之后,接下 来的问题就可以转换成在最小生成树上求任意两点之间距离的平均值,对于每条边,统计所 有的路径用到此边的次数,也就是边的两端的点数之积。那么这条边的总贡献就是次数...
07月20日 2,614
  1. .01 4:06
  2. .02 1:47
  3. .03 3:39
  4. .04 1:40