10.29 多校联测
30+35+0+0 = 65 菜就多练
T1:
题意：给定一棵以1为根的树，从节点1出发，如果当前节点有儿子没走过，可以花费对应边权的时间走到儿子，否则不花费时间走回父结点。每个点带权值，要求最小化到达节点时间乘点权总和。
解：
非常明确的贪心，对于子树内部最优路径必然确定，只要考虑先后顺序即可，直接贪心。（考场试cmp猜错了qwq)
考虑cmp比较什么：子树点权和\边权和
对于这种先考虑两个儿子的情况，再去扩展。
子树内的贡献无法改变，直接考虑对后手的影响，于是有:
\[e_i \times w_{i+1} < e_{i+1} \times w_i \]推广仍然正确。
T2：
题意：给一棵树，有 \(m\) 次操作，每次给两个点（可能是同一个点），以这两个点为根的子树染上新颜色（每次操作颜色不同，一个点同时有多种颜色），求每个点有多少点和它有一样的颜色。
分析：是我非常熟悉的可持久化线段树，没救了
考场在想类似线段树合并一类的（从下往上），但这里从上往下信息具有传递性，直接可持久化即可。
解：
首先一个点的某一个祖先被染色了，那以这个祖先为根的子树都会被染上一种颜色。如果每次只有一个点，那问题就很简单了。考虑另一个点的影响，如果同一操作的两个点不会互相包含，那就只好打标记了，对于每个节点 \(u\) 可以把它同一次操作的另一个点的子树全标记了，这些信息对子树有推广所以dfs时直接可持久化就做完了。
T3：
题意：
有编号从 $ 1 $ 到 $ N $ 的 $ N $ 家烧烤店，烧烤店在一条线上按照编号顺序排序，第 $ i $ 家烧烤店与第 $ i + 1 $ 家烧烤店的距离是 $ A_i $ 。
你有编号从 $ 1 $ 到 $ M $ 的 $ M $ 张烧烤券，不管是在哪一家烧烤店都可用烧烤券来吃烧烤，在第 $ i $ 家烧烤店用烧烤券 $ j $ 可以吃到一顿美味度为 $ B_{i,j} $ 的烧烤，每一张烧烤券只能使用一次，但是在一家烧烤店你可以使用任意多张烧烤券。
你想从自己选择的一家烧烤店开始（随意选择一个开始），然后不断地用未使用的烧烤券去另一家烧烤店。你最终的幸福值是所吃所有烧烤的美味度减去所走的总路程。求最大可能的最终幸福值（ $ M $ 张券必须用完）。
感觉不是很难的题？，但不会（雾
解：
首先最优答案是一段区间 \([L,R]\) ，并选择每一种烧烤在区间内的最大美味度。
直接暴力RMQ \(O(n^2m)\)
然后就是有些套路的，考虑某一份烧烤在哪一段区间内会有贡献，可以单调栈维护，然后变成二维差分（二维数点的套路），单点查询即可。（yysy,这的有些套路了，还得多练）
题目还有关于决策单调性的一些做法？有空补。
T4：
疑似拉插？问候出题人
标签：总结,十一月,子树,一个点,题意,烧烤店,烧烤,节点,模拟 From： https://www.cnblogs.com/e-kid/p/18513958