2020-2021:teams:farmer_john:week_18
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:week_18 [2020/09/04 17:50] jjleo [题目] |
2020-2021:teams:farmer_john:week_18 [2020/09/04 17:53] (当前版本) jjleo [JJLeo] |
||
|---|---|---|---|
| 行 34: | 行 34: | ||
| * 题意：给你一棵$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$相同。下面通过构造证明这个必要条件也是充分的。 | ||
| 行 58: | 行 58: | ||
| * 分类：树形dp。 | * 分类：树形dp。 | ||
| - | * 题意：给定一棵$n$个节点的树，每个节点有两个权值$a_i,b_i$，要求将树分为数条互不相交的链，每条边都必须被划分，点可以重复，且每条链的$a_i$单调（非严格单增或单减），求所有链的$b_i$之和的最小值。$(n \le 10^5)$ | + | * 题意：给定一棵$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)$。 | * 题解：先考虑所有边都各自成一条链，然后再对边进行合并从而减少答案。考虑给边进行定向，由$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)$。 | ||
2020-2021/teams/farmer_john/week_18.1599213014.txt.gz · 最后更改: 2020/09/04 17:50 由 jjleo
