「CF353E」 Antichain-乱搞📅 Mar 2, 2019 · ✏️ 650 words · ☕ 2 mins read给定一个长度为 n 的 01 序列,第 i 位是 0 代表 节点 i 到节点 imodn+1 有一条有向边,第 i 位是 1 代表 节点 imodn+1 到节点 i 有一条有向边。我们称一个节点对 (u,v) 是妙的当且仅当不存在 u 到 v 和 v 到 u 的路径任何两者之一。现在你要从这个图里面挑出一个集合,使得集合中任意两个不同的节点 u 和 v 之间构成的节点对 (u,v) 都是妙的。请你输出这个集合的大小的最大值。
「CF804D」Expected diameter of a tree-树的直径+乱搞📅 Feb 15, 2019 · ✏️ 1006 words · ☕ 3 mins read给定一个含有 n 个点, m 条边的森林。有 q 个询问,每次给出两个点 ui,vi ,如果 ui 在联通块 A 内,vi 在联通块 B 内,我们随机选择两个点 a∈A,b∈B ,我们在 (a,b) 之间连一条边,如果这个连接成后新联通块不构成一个树,输出 −1 ,否则输出新联通块树的直径的期望。所有边权均为 1 。