Codeforces 1059E. Split the Tree (树上贪心)

日付: 10月 07, 2018

[Problem - E - Codeforces](https://codeforces.com/contest/1059/problem/E)

## Problem

一棵树分割为若干条垂直路径(只能从上到下)，每条路径结点数不大于L，权值和不大于S，求最小分割条数。

数据范围： \\( 1\le n \le 10^5 \\), \\(1\le L \le 10^5\\), \\(1\le S \le 10^{18}\\)

## Solution

由垂直路径的定义，只能是某个结点到根结点路径上的一段。考虑从叶子结点出发，维护当前结点所在路径的结点数和权值和，
当多条路径交汇于结点\\(u\\)的时候，有两种情况：1. 在结点\\(u\\)处新开一条路径；2. 结点\\(u\\)和某一条路径合并，其他路径断开。
当没有路径可以与\\(u\\)合并时取情况1。对于情况2，贪心选择能够回溯到最靠近根结点的一条。答案就是情况1遇到的次数。

查找回溯位置的方法。首先，在dfs时，当前结点为\\(u\\)，子结点为\\(v\\)(代表待处理的路径)，\\(Cnt[v]\\)和\\(Sum[v]\\)分别表示路径v的结点数和权值和。
从u开始向上回溯的段需要满足结点数不大于\\(L-Cnt[v]\\)，权值和不大于\\(S-Sum[v]\\)。对于前者，直接可以得到回溯最浅深度，对于后者，可以
预计算所有结点的权值前缀和\\(PreSum\\)，然后倍增找到\\(u\\)的最远祖先满足\\(PreSum[u]-PreSum[p] \le S - Sum[v]\\)，回溯最浅深度为\\(Depth[p]+1\\)。
对于\\(v\\)，算出两个限制条件下的回溯最浅深度后取\\(min\\)，如果该深度比\\(u\\)大，说明无法合并。
最后将\\(u\\)与可以合并且回溯最浅深度最小(如果存在的话)的\\(v\\)合并，算出\\(Cnt[u]\\)和\\(Sum[u]\\)的值。

## Code

[Submission #43883391 - Codeforces](https://codeforces.com/contest/1059/submission/43883391)

## Tips

树上倍增方法，首先一次dfs预计算一个\\(Fa[u][i]\\)数组，表示结点\\(u\\)向上\\(2^i\\)的祖先，对于溢出的情况，取树的根结点或者不存在的结点。
倍增时，一定要从大到小枚举\\(i\\)
```cpp
// 计算Fa数组
void dfs(int u, int p) {
    ...
    Fa[u][0] = p;
    for (int i=1;i<=18;i++) Fa[u][i] = Fa[Fa[u][i-1]][i-1];
    ...
}

// 倍增
int p = u;
for (int i=18;i>=0;i--) {
    int tp = Fa[p][i];
    if (tp is valid) p = tp;
}
```

KONGROOの基地

このブログを検索

Codeforces 1059E. Split the Tree (树上贪心)

コメント

コメントを投稿