中间有几场感觉没什么必要写blog就咕了算了 ~
另外，这场也只打算写 T1,T2 两道的博客（因为这两个是我现写的）
# 前言
虽然都是搬来的题，但是好像搬题也不轻松啊……纠结死了 QwQ
所以干脆就来一场纠结的比赛算了……
# 题意
T1. 纠结的洗衣店 wash
有 $k$ 件衣服，$n$ 台洗衣机，$m$ 台烘干机。
每件衣服需要先洗再烘干。一台洗衣机一次只能洗一件衣服，一台烘干机一次只能烘干一件衣服。
第 $i$ 台洗衣机洗一件衣服要 $a_i$ 的时间，第 $i$ 台烘干机烘干一件衣服要 $b_i$ 的时间。
求花费的最小时间。
数据规模：$1\le n,m\le10^5$，$1\le k\le10^5$，$0\le a_i,b_i\le10^9$。
T2. 纠结的旅行 travel
一棵 $n$ 个节点的树，每条边 $e$ 有权值 $a_e,b_e$，每个点 $u$ 有权值 $c_u,d_u$。定义一条从 $s$ 出发的路径 $P$ 的权值为：
对于每个 $s$，求从 $s$ 出发的所有简单路径的权值之和（路径不能只含一个点）。
数据规模：$2\le n\le10^5$，$0\le a_e,b_e,c_u,d_u\le10^5$。
# 解析
T1. wash
考虑如果只洗衣服怎么做（题目中也有这个的部分分）。有一种强烈的感觉可以贪心。
但是怎么贪心？我们要让洗完所有衣服的时间——洗好最后一件衣服的时间最小。于是可以用堆维护当前这件衣服放在每台洗衣机中洗好的时间，当然要取这些值中最小的。
稍微证明一下：维护 $t_i$ 表示当前这件衣服放进第 $i$ 台洗衣机洗完的时刻，显然 $t_i$ 是随着放入衣服而不断递增的。
因此，由于所有衣服都是一样的，如果当前这件衣服取最小的 $t_x$ 是不优的，那么所有衣服此时取 $t_x$ 都是不优的，也就是说 $t_x$ 空着了。
但是因为 $t_x$ 是现在 $t_i$ 中最小的，之后一定仍然是 $t_i$ 中最小的（因为 $t_i$ 只可能增加），显然对于最后一件衣服，取 $t_x$ 一定比取其他 $t_i$ 优。得证。
这样可以得到第 $i$ 件衣服什么时候洗好，记为 $p_i$。
再考虑有烘干机。
我们惊奇地发现烘干机倒过来看就是洗衣机。于是可以“倒过来”用相同的贪心求出每件衣服什么时候烘干完，记为 $q_i$。
于是把 $p_i,q_i$ 搭配一下，然后求 $\max\{p_i+q_i\}$ 就是最终答案。根据浅薄的贪心知识，显然把 $p_i$ 从小到大排序，$q_i$ 从大到小排序，然后匹配起来 $\max\{p_i+q_i\}$ 的值最小。
T2. travel
考虑一条边 $e$ 什么时候取 $a_e+c_s$ 或 $b_e+d_s$——当 $a_e+c_s\le b_e+d_s$ 时取 $a_e+c_s$，然后是一个常见套路——相同下标挪到一边，条件等价于 $a_e-b_e\le d_s-c_s$。
于是维护一下 $a_e-b_e$，对于每个起点 $s$ 就知道该取什么值了。
把现在的起点 $s$ 设为整棵树的根。在此意义下，定义 $siz_u$ 为 $u$ 的子树大小，$to_e$ 表示边 $e$ 的两端点中深度较大的一个，不难得到 $s$ 的答案：
按照之前的思路，分离一下：
再分离成4部分
可见我们要维护 $siz_{to_e}\times a_e$,$siz_{to_e}\times b_e$,$siz_{to_e}$。这些大于小于该怎么维护？不难想到树状数组。
又因为这道题的计算跟起点 $s$ ——树的根节点关系很大，于是可以用换根DP。每次换根只会有一个 $siz_{to_e}$ 发生改变，因此维护是 $O(\log n)$ 的，总的复杂度就是 $O(n\log n)$ 的。