没什么好说的，一题不会。
D1T1. 面基之路
考虑瓶颈在于最后一个网友的面基时间。
Trick：可以看作 所有网友都在同一时间（显然一定也是同一位置）面基，因为各个网友和 hehe 桑本人都是独立行动，而且可以原地不动。
也就是求一个最快的集合点（包括顶点和各边的中点）。直接边转点，枚举最短路之和最小的点即可。
D1T2. 机器人
题意：给出其一个长度为 \(n\) 的（不一定合法的）括号序列，求任意插入 \(t\) 对括号，形成的最终串的方案数。\(n\le 300\)。
实际是双序列匹配类型的 DP，设出两维 \(i,j\) 表示插入 \(i\) 对括号的串和原串的前多少位相匹配的方案，这里只需要后者是前者的子序列。
然后这个计数的去重是大问题，因为不能暴力枚举新加的右括号和之前的匹配，否则子问题会变成区间 DP。但是任意匹配显然是可能算重的。
仔细考虑重复的原因，发现就在于虽然加入了 \(t\) 对括号，但是也可能最后一些是和 原串中 的括号匹配。
考虑贪心转移来防止重复，记录多一维状态 \(k\) 表示多出多少个左括号，考虑加入一对括号的转移：
-
若之前有没有被匹配的 新加入 左括号，或者决定新加入的左括号与它是 连续的，右括号匹配之并减小 \(k\) 转移。
-
要么尝试让右括号和原串匹配。即预处理一个 \(p_i\) 表示 原串中 从 \(i\) 开始向前扫描的第一个没有匹配右括号的左括号位置。
-
否则让新加入的两个括号匹配。
D1T3. 稳健型选手
猫树分治 适用于：区间信息 难以多次合并，容易单次合并，容易首尾插入。