(题解由比赛出题人提供，点击标题可开始做题）
T1 Treepath
观察到路径 x->y 的长度的奇偶性只与 x 到根的长度的奇偶性以及 y 到根的 长度的奇偶性有关（令 dist[x]表示 x 到根的距离，x 到 y 的距离为dist[x]+dist[y]-2dist[lca]，最后一项对奇偶性没影响，所以真正有用的信息包含 在 dist[x]和 dist[y]里，不难想到当这两个数奇偶性相同时路径长度为偶数）。复杂度O(n)。
T2 Xorto
首先观察到[l..r]的异或和等于[1..l-1]的异或和异或上[1..r]的异或和，所以问 题就变成了在 n 个数中找 4 个数，使得 4 个数的异或和为 0 且第二个数和第三 个数不在同一位置，所以我们可以枚举第一个区间的右端点，第一个区间的左 端点同样通过枚举计算，同时拿一个 map 维护在枚举的右端点右边的区间的异 或和出现的情况，随着右端点左移，map 里维护的区间信息越来越多。复杂度 O(n^2logn)。
T3 MMSet2
不难发现答案就是 
。
证明可以这样考虑：
二分答案d,判断是否存在一个点u，使得 f(u)≤d。也就是
。即以S中的每个点为圆心，画一个半径为d的圆，这些圆都包括了u。
那么存在这样一个u就表示这些圆都有交。若d<L，直径端点的两个圆无交，若d=L，因为任意两个点的距离 ≤ 直径，因此任意两个点的圆都有交。所以L是d的最小值。
点集直径很好求。当然可以建个虚树DP一下，不过这样就要排序，复杂度带log了。
注意到一个事实：令dia(T)=(a,b)表示T的直径是a,b，那么
。证明可以这样考虑：
二分答案d,判断是否存在一个点u，使得 f(u)≤d。也就是
。即以S中的每个点为圆心，画一个半径为d的圆，这些圆都包括了u。那么存在这样一个u就表示这些圆都有交。若d<L，直径端点的两个圆无交，若d=L，因为任意两个点的距离 ≤ 直径，因此任意两个点的圆都有交。所以L是d的最小值。
点集直径很好求。当然可以建个虚树DP一下，不过这样就要排序，复杂度带log了。
注意到一个事实：令dia(T)=(a,b)表示T的直径是a,b，那么
T4 Color
答案是最大度数，必要性显然。构造法是随便顺序染色，如果一条边卡死了，就说左边的点只剩红色，右边的点只剩蓝色，那就在红蓝两种颜色的边上做一下增广。因为是二分图，一定可以增广。另一种构造法是每次贪心最大匹配，优先匹度数大的点，这样可以保证所有最大度数的点都被匹到。匹完了用一种颜色染，再删除就行。
T5 Cut
一个割的权值就是集合中点权值的异或(点权值就是和他相邻的边权值的异或。)(集合取割的两个集合中哪一个都行。)理由是这样的话集合内的边恰好算了0或者2次，集合之间的算了一次。这样就转化成一些数字随便选一些异或起来的可能答案和，就很好统计了。
其他疑问可加以下交流群（加入一个即可啦~）
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305
全部评论
(0) 回帖