CF516D Drazil and Morning Exercise
给定一棵 (n) 个点的带边权树，定义 (f_u=max_{i=1}^noperatorname{dist(u, i)})
(q) 次询问，每次给定 (l) ，求满足 (max_{uin S}f_u-min_{uin S}f_uleq l) 的连通块 (S) 包含的点数的最大值
(nleq10^5, qleq50)
让 (f_u) 取得最值的 (i) 一定是直径的两端之一，暴力求即可（也可以换根dp
容易想到对于每个询问，枚举每个 (u) 作为连通块 (S) 中的 (min) 或 (max) ，将 (f_u) 排序后即为考虑连续的一段点构成的连通块
考虑枚举 (min) ，用并查集维护集合连通情况，降序排序，双指针扫的时候会删掉 (f_v-f_u>l) 的点 (v) ，此时 (v) 一定是叶子，将 (v) 所在的连通块答案 (-1) 即可
bzoj3569 DZY Loves Chinese II
给定一张 (n) 个点 (m) 条边的无向图， (q) 次询问，每次给出一个边集 (S) ，问删掉边集中的所有边后图是否联通，询问独立，强制在线
- (nleq10^5, mleq5 imes10^5)
- (qleq5 imes10^4; |S|leq15)
找到原图中的任意一棵生成树，图不连通当且仅当，存在一条树边，使得它被删了，并且连接生成树分成的两部分的边也都被删了
对于一条非树边 ((u, v)) ，给它赋一个随机值 (x) ，并将生成树上路径 ((u, v)) 上的所有树边的权值异或上 (x) 。容易发现，删掉边集 (S) 后图不连通，当且仅当 (exist Tsubseteq S, displaystyleoplus_{xin T}x=0)
然后线性基搞搞，时间复杂度大概是 (O(log w imesdisplaystylesum |S|)) ，其中 (w) 是随机值域范围
貌似是一种常见套路。。
CF1344D Résumé Review
给定一个长为 (n) 的整数数组 (a_i) 和常数 (k) ，求出长为 (n) 的整数数组 (b_i) 满足：
- (0leq b_ileq10^9)
- (displaystylesum_{i=1}^nb_i=k)
- 最大化 (displaystylesum_{i=1}^nb_i(a_i-b_i^2))
(nleq10^5; a_iin[0, 10^9])
令 (f_i(x)=x(a_i-x^2)) ，容易发现该函数是凸的
考虑二分凸函数斜率，每次二分 check 中再对每个点二分出斜率对应的 (b_i) ，二分完成后不一定满足条件 (displaystylesum_{i=1}^nb_i=k) ，随便搞搞即可
外层是个 wqs二分，时间复杂度 (O(nlog^2v))
杂题
给定一张 (n) 个点的无向图，统计本质不同的团的数量
(nleq50)
时限 10s
考虑折半，对于左侧预处理出 (f_S=[) 点集 (S) 是一个团 (]) ，右侧同理处理出 (g_S)
可以再处理出 (A_S) 表示有多少个左侧点集与右侧点集 (S) 形成了一个团，这个可以高维前缀和处理出来，答案即为 (displaystylesum A_Sg_S)
时间复杂度 (O(n2^{frac n2}))
杂题
有 (n) 个元素 (a_i) ，你每轮可以选择两个数 (i, j (i>j)) ，给答案增加 (a_i-a_j) ，并删掉 (a_i, a_j) ，当然，这一轮也可以不操作
求出如果进行 (1simlfloorfrac{n}{2} floor) 轮操作，答案最大是多少
(nleq10^5)
可以费用流，源点 (S) 向每个点 (i) 连容量为 (1) ，费用为 (a_i) 的边，每个点 (i) 向汇点 (T) 连容量为 (1) ，费用为 (-a_i) 的边，每个点 (i) 向点 (i-1) 连容量为 (+inf) ，费用为 (0) 的边，跑最大费用最大流
显然每流一轮，路径形如 (S o i, i o j, j o T) ，如果 (i>j) ，含义显然时在这一轮选择了 (i, j) 这两个数；如果 (i<j) ，则 (i o j) 之间的边容量必定 (>0) ，这个操作相当于打乱了原来的一轮操作，例如之前有一轮操作 (S o u, u o v, v o T) ，其中 (u>j, v<i) ，这轮操作相当于将操作 ((u, v)) 取消，新增匹配 ((u, j)) 和 ((i, v))
这样每流一轮就相当于进行了一轮操作。若某一轮流流出的费用 (<0) ，则答案不会增加， break 即可
可以暴力模拟费用流以做到 (O(n^2)) ，每轮操作，要么找到一对没用过的 (i, j (i>j)) 使得 (a_i-a_j) 最大，要么找到一对 (i, j (i<j)) 使得路径 (i o j) 之间所有流量 (>0) ，且 (a_i-a_j) 最大
可以用一些奇妙做法做到 (O(nlog n))
杂题
给定一棵 (n) 个点的树，第 (i) 个点点权为 (w_i) ，你需要给树添加一条不存在的边，最大化 (displaystylesum_{i=1}w_i imes dep_i) ，其中 (dep_i) 是节点 (i) 到环的最短距离，特别的，环上的点深度为 (0)
- (nleq10^6)
- (|w_i|in[-10^3,10^3])
任选一个点为根，考虑统计点 (u) 作为所连边 ((x, y)) 的 (lca) 时的答案
记 (f_u) 为从 (u) 的子树中选一个点 (v) ，将 (u, v) 链上的点作为环点时， (u) 子树内的答案
这个很容易转移，可能要判一下环长必须大于 (2)
子树外的答案就维护 (w_i imes dis(i, u)) ，可以 换根dp 一下
现在可以由 (f_u) 直接统计所有父子链答案
对于 (u=operatorname{lca}(x, y)) 的答案，能够直接考虑 (vin son(u), f_v) 的最值
就做完了。。
杂题
你需要维护一个字符串序列 ({S_n}) ，其中有 (n) 个字符串，初始全为空。接下来有 (q) 次操作，支持两种操作，下面设当前为第 (i) 次操作，且本题中字符集为 ([1, q]cap N_+)
1 l r，表示在所有编号在 ([l, r]) 内的字符串末尾添加字符 (i) ，这里 (i) 是一个 ([1,q]) 范围内的整数2 l r，表示询问所有编号在 ([l,r]) 内的字符串的最长公共子序列长度(n, qleq10^5)
容易发现区间 ([l, r]) 的 LCS 长度是完全包含区间 ([l, r]) 的操作个数，三维偏序即可
杂题
给定一张 (n) 个点 (m) 条边的带正边权无向图，对每个点求出包含它的所有出边时，最小生成树的权值
(nleq10^5; mleq3 imes10^5)
LCT 被卡常了
有一个高论做法，之后填坑（咕了）