2020-2021:teams:farmer_john:2020暑假精选题目:树上问题
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020暑假精选题目:树上问题 [2020/09/04 15:23] jjleo [题解] |
2020-2021:teams:farmer_john:2020暑假精选题目:树上问题 [2020/09/05 11:54] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 23: | 行 23: | ||
| 第二种情况是一个定值，因此对于每一个 $v$ 我们可以二分出满足第一种情况的 $u$ 的个数，剩余的即为第二种情况。最后答案要用 $map$ 记录下来避免重复询问。复杂度是神奇的 $O(n\sqrt{n}\log{n})$ | 第二种情况是一个定值，因此对于每一个 $v$ 我们可以二分出满足第一种情况的 $u$ 的个数，剩余的即为第二种情况。最后答案要用 $map$ 记录下来避免重复询问。复杂度是神奇的 $O(n\sqrt{n}\log{n})$ | ||
| - | =====CF1936E===== | + | =====CF1396E===== |
| ====题意==== | ====题意==== | ||
| 给你一棵$n$个节点的树，保证$n$为偶数，边权为$1$，问是否存在一个完美匹配，使得两两点之间距离之和恰好等于$k$。$(n \le 10^5, k \le n^2)$ | 给你一棵$n$个节点的树，保证$n$为偶数，边权为$1$，问是否存在一个完美匹配，使得两两点之间距离之和恰好等于$k$。$(n \le 10^5, k \le n^2)$ | ||
| ====题解==== | ====题解==== | ||
| - | 我们考虑一条边，它将整棵树分为两部棵子树，大小分别为$x$和$n-x$，两者奇偶性相同。所有两点位于两侧的匹配都会经过这条边，而其它匹配一定是在各自子树内完成的，因此这条边被经过的次数的奇偶性一定和$x$相同，同时也有一个显然的上界$\min(x,n-x)$，设该边贡献的权值为$a$，则有$(x \mod 2 )\le a \le \min(x, n - x)$。 | + | 我们考虑一条边，它将整棵树分为两棵子树，大小分别为$x$和$n-x$，两者奇偶性相同。所有两点位于两侧的匹配都会经过这条边，而其它匹配一定是在各自子树内完成的，因此这条边被经过的次数的奇偶性一定和$x$相同，同时也有一个显然的上界$\min(x,n-x)$，设该边贡献的权值为$a$，则有$(x \mod 2 )\le a \le \min(x, n - x)$。 |
| 我们以树的重心为根，那么除了根节点外，以每个节点为根的子树都小于另一部分，即$\min(x,n-x)=x$，因此对于每一条边我们可以得到公式$\sum (siz_i\mod 2) \le k \le \sum siz_i$，且$k$的奇偶性和$\sum siz_i$相同。下面通过构造证明这个必要条件也是充分的。 | 我们以树的重心为根，那么除了根节点外，以每个节点为根的子树都小于另一部分，即$\min(x,n-x)=x$，因此对于每一条边我们可以得到公式$\sum (siz_i\mod 2) \le k \le \sum siz_i$，且$k$的奇偶性和$\sum siz_i$相同。下面通过构造证明这个必要条件也是充分的。 | ||
| 行 35: | 行 35: | ||
| 我们每次考虑根节点的各个子树，每次都考虑未匹配节点数最多的那个子树，我们每次将该子树中的两个点$x,y$进行匹配（而不是像上述所说各自匹配到根节点另外子树的节点），对最终权值的减少量为$2 \cdot dep_{\operatorname{lca}(x,y)}$，因此我们只需不断地寻找两个合适的点进行匹配，使得最终权值不断减少直到$k$。最后，因为我们每次都相当于让最大子树的节点数减少两个，因此根节点一直都是重心，最后只需将剩余点按dfn序排序，贪心地令$i$和$i+\frac{|v|}{2}$匹配即可（类似2020牛客第二场那题）。 | 我们每次考虑根节点的各个子树，每次都考虑未匹配节点数最多的那个子树，我们每次将该子树中的两个点$x,y$进行匹配（而不是像上述所说各自匹配到根节点另外子树的节点），对最终权值的减少量为$2 \cdot dep_{\operatorname{lca}(x,y)}$，因此我们只需不断地寻找两个合适的点进行匹配，使得最终权值不断减少直到$k$。最后，因为我们每次都相当于让最大子树的节点数减少两个，因此根节点一直都是重心，最后只需将剩余点按dfn序排序，贪心地令$i$和$i+\frac{|v|}{2}$匹配即可（类似2020牛客第二场那题）。 | ||
| - | 具体实现过程我们只需要开个大根堆维护最大的子树，再开个set维护每个子树中存在一个及以上儿子的节点（不然没办法让它成为$\lca$）及其深度，并且每次优先选择最深的点删除即可。 | + | 具体实现过程我们只需要开个大根堆维护最大的子树，再开个set维护每个子树中存在一个及以上儿子的节点（不然没办法让它成为$\operatorname{lca}$）及其深度，并且每次优先选择最深的点删除即可。 |
| + | |||
| + | =====CF1394D===== | ||
| + | |||
| + | ====题意==== | ||
| + | 给定一棵$n$个节点的树，每个节点有两个权值$a_i,b_i$，要求将树分为数条互不相交的链，每条边都必须被划分，点可以重复，且每条链的$a_i$单调（非严格单增或单减），求所有链的$b_i$之和的最小值。$(n \le 2 \times 10^5)$ | ||
| + | ====题解==== | ||
| + | 先考虑所有边都各自成一条链，然后再对边进行合并从而减少答案。考虑给边进行定向，由$a_i$小的点指向大的点；如果两个点$a_i$相同那么边的方向任意，需要在后续dp过程中进行讨论。设$f_i$为以$i$为根的子树中若$i$与它父亲的边向下所能减少的最大权值，$g_i$为以$i$为根的子树中若$i$与它父亲的边向上所能减少的最大权值，$S_i$为节点$i$的子节点集合，那么有$$f_i=\max_{S\in S_i}(\sum_{j\in S}f_j+\sum_{j \notin S \operatorname{and} j \in S_i}g_j+ b_i \cdot \min(|S|,|S_i|-|S|+1))$$ $$g_i=\max_{S\in S_i}(\sum_{j\in S}f_j+\sum_{j \notin S \operatorname{and} j \in S_i}g_j+ b_i \cdot \min(|S|+1,|S_i|-|S|))$$ 前面的式子不好处理，我们可以化简得到$$\sum_{j\in S}f_j+\sum_{j \notin S \operatorname{and} j \in S_i}g_j=\sum_{j\in S_i}g_j + \sum_{j \in S}(f_j-g_j)$$ 前者为定值，我们可以将子节点的$f_j-g_j$从大到小排序，设为$sum_i$，同时设$cnt_i$为节点$i$的子节点数，则有$$f_i=\sum_{j\in S_i}g_j+max_{j=0}^{cnt_i}(sum_j+b_i \cdot \min(j,cnt_i-j+1))$$ $$g_i=\sum_{j\in S_i}g_j+max_{j=0}^{cnt_i}(sum_j+b_i \cdot \min(j+1,cnt_i-j))$$ 最后根节点的答案特判一下，即为$$root_i=\sum_{j\in S_i}g_j+max_{j=0}^{cnt_i}(sum_j+b_i \cdot \min(j,cnt_i-j))$$时间复杂度$O(n \log n)$。 | ||
| + | |||
| + | =====CF1303G===== | ||
| + | |||
| + | ====题意==== | ||
| + | 定义一个序列$[s_1, s_2, \dots, s_k]$的前缀前缀和为$s_1 + (s_1 + s_2) + (s_1 + s_2 + s_3) + \dots + (s_1 + s_2 + \dots + s_k)$。\\ | ||
| + | 给出一棵$n$个节点的树，每个点有一个权值，求一条有向路径，使得每个点权值所构成的序列的前缀前缀和最大。$(2 \le n \le 150000)$ | ||
| + | ====题解==== | ||
| + | 看到路径问题，直接上点分治，我们考虑两条路径合并时如何计算前缀前缀和。我们规定其它节点到分治中心的方向为向上，反之为向下。考虑所有向上路径对向下路径的贡献，设向上路径的前缀前缀和为$b$，所有节点权值之和为$x$，向下路径的前缀前缀和为$a$，节点数为$k$，则该路径的总前缀前缀和$y$为$$y=(kx+b)+a$$其中括号内是一个一次函数的形式而$a$是一个定值，因此问题转化为多个一次函数求横坐标为某一值时的最大值，直接使用LineContainer即可。 | ||
| + | |||
| + | 注意我们每条路径向上向下均有可能，因此每一个分治中心要进行两次，一正一反。另外分治中心我们并没有考虑，编写时无论将其放在向下或向上均可，还需要注意存在分治中心为一个端点的向上或向下的路径答案，不要忘记特判。 | ||
2020-2021/teams/farmer_john/2020暑假精选题目/树上问题.1599204182.txt.gz · 最后更改: 2020/09/04 15:23 由 jjleo
