摘要:
给定一棵由 N N 个点组成的以点 R R 为根的多叉树,有 M M 次询问,每次给定两个节点 u , v u,v,你需要求出这两个节点的 最近公共祖先。 【名词解释】 最近公共祖先(LCA):两个节点在树中深度最大的共同祖先节点。 输入描述: 第一行包含三个正整数 N , M , R ( 1 ≦ 阅读全文
摘要:
描述 露米娅作为宵暗的妖怪,非常喜欢吞噬黑暗。 这天,她来到了一条路上,准备吞噬这条路上的黑暗。 这条道路一共被分为 n n 部分,每个部分上的黑暗数量为 a i a i 。 露米娅每次可以任取 连续的 未被吞噬过的 三部分,将其中的黑暗全部吞噬,并获得中间部分的饱食度。 露米娅想知道,自己能获 阅读全文
摘要:
给定一个由 n n 个正整数组成的数组 { a 1 , a 2 , … , a n } {a 1 ,a 2 ,…,a n }。请你计算该数组的最长不下降子序列(Longest Non-decreasing Subsequence,简称 LNDS)长度。 对于一条子序列,要求保留原数组中的 阅读全文
摘要:
给定一棵有 n n 个点构成的树,点的编号依次为 1 1 到 n n,每个点都有点权 a i a i ,你需要删除所有 n − 1 n−1 条边。 其中,每删除一条边的代价为:与这条边相连的两个连通块中,各自的最小点权之和。换句话说,设两个连通块中的最小点权分别为 x x 与 y y,则本次代价 阅读全文