领导集团问题「FJOI2018」

【题目描述】一个公司的组织领导架构可以用一棵领导树来表示。公司的每个成员对应于树中一个结点$v_i$,且每个成员都有响应的级别$w_i$。越高层的领导,其级别值$w_i$越小。树中任何两个结点之间有边相连,则表示与结点相应的两个成员属于同一部门。领导集团问题就是根据公司的领导树确定公司的最大部门。换句话说,也就是在领导树中寻找最大的部门结点子集,使得的结点$v_i$和$v_j$,如果$v_i...

树的旋转「POI 2011」

【题目描述】现在有一棵二叉树,所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有$n$个叶子节点,满足这些权值为$1\dots n$的一个排列)。可以任意交换每个非叶子节点的左右孩子。 要求进行一系列交换,使得最终所有叶子节点的权值按照遍历序写出来,逆序对个数最少。 【输入格式】第一行n下面每行,一个数x 如果$x=0$,表示这个节点非叶子节点,递归地向下读入其左孩子和右孩子的信息,...

永无乡「HNOI2012」

【题目描述】永无乡包含 n 座岛,编号从 1 到 n,每座岛都有自己的独一无二的重要度,按照重要度可 以将这 n 座岛排名,名次用 1 到 n 来表示。某些岛之间由巨大的桥连接,通过桥可以从一个岛 到达另一个岛。如果从岛 a 出发经过若干座(含 0 座)桥可以到达岛 b,则称岛 a 和岛 b 是连 通的。现在有两种操作:B x y 表示在岛 x 与岛 y 之间修建一座新桥。Q x k 表示询...