首页 > Genealogy in the trees

XFlypig

发表于 2023-09-08 22:25:51

不清楚正解, 但树套树真的能过 (1800ms) 题目要求即为求满足如图所示的{a, b, p, q} 对数即对于每一个{a, b} 都要快速求出到的路径上, 存在所对应的在的子树里首先想到树剖, 发现线段树维护的是一段区间内所有点的对应点在的子树里的个数, 直接在树剖的展开全文

工口发动机

发表于 2023-09-09 18:56:49

Genealogy in the trees 感觉题解太智力了，写个不带脑子的大暴力做法。给定个点对，次询问，对每次询问的点对查询有多少点对满足是的祖先，是的祖先。树上问题考虑转换成序列问题，先转换到dfs序上。考虑拆解查询，满足是的祖先这个条件在重展开全文

itoshiki_Treap

发表于 2023-10-18 22:18:35

D Genealogy in the trees 考虑把树拍平到 dfn 序列上，那么题目要求即为对于每个求有多少点对满足：其中为点子树大小，但本式中最后一部分不需要显式处理，只需在结点退栈时记录时间戳即可。放到二维平面上，将第一个式子的元素作为轴坐标，第二个式展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛