Warning: session_start(): open(/tmp/sess_b99f061bd10939eb4c027f0b4d933ab3, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 2022.07.23 牛客多校第三场 ====== ===== 题解 ===== ==== A ==== 本题的重点在于：给一棵树，以及k个关键点，问去掉任意一个关键点后，剩下k-1个节点的lca的变化。 赛时观察到只有有限的情况下，lca会变化。 可以先求出k个点的lca，再统计其各个子树中有多少关键点。 * 若只有一个子树有关键点，则lca自身必为关键点，此时只有去掉lca自身，剩下的lca才会改变。 * 若只有两个子树有关键点，则只有去掉只含一个关键点的子树才会改变lca。 * 若更多子树有关键点则lca不会变化。 赛后其他队伍更简单的做法： - 统计前缀lca和后缀lca，去掉其中一个点后的lca就是一段前缀lca和一段后缀lca的lca。 - 若干点的lca等价于这些点中dfs序最小和dfs序最大的节点的lca。 ==== C ==== 排序字符串。对于串a和串b，若ab,greater>导致一直超时