首页 > Genealogy in the trees
开通博客写题解
头像 XFlypig
发表于 2023-09-08 22:25:51
不清楚正解, 但树套树真的能过 (1800ms) 题目要求即为求满足如图所示的{a, b, p, q} 对数 即对于每一个{a, b} 都要快速求出 到 的路径上, 存在 所对应的 在 的子树里 首先想到树剖, 发现线段树维护的是一段区间内所有点的对应点在 的子树里的个数, 直接在树剖的 展开全文
去ta的博客 赞 (6) 回复(4) 收起
头像 工口发动机
发表于 2023-09-09 18:56:49
Genealogy in the trees 感觉题解太智力了，写个不带脑子的大暴力 做法。 给定 个点对， 次询问，对每次询问的点对 查询有多少 点对 满足 是 的祖先， 是 的祖先。 树上问题考虑转换成序列问题，先转换到dfs序上。 考虑拆解查询，满足 是 的祖先这个条件在重 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 itoshiki_Treap
发表于 2023-10-18 22:18:35
D Genealogy in the trees 考虑把树拍平到 dfn 序列上，那么题目要求即为对于每个 求有多少点对 满足： 其中 为点 子树大小，但本式中最后一部分不需要显式处理 ，只需在结点 退栈时记录 时间戳即可。 放到二维平面上，将第一个式子的元素作为 轴坐标，第二个式 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”