PermuTree (Hard Version)

前往 算竞题解 分类 || 前往 算竞模板 分类

原题链接

E2-PermuTree (Hard Version) Codeforces Round 890 (Div. 2) supported by Constructor Institute

简明题意

给定一棵 nn 个节点的有根的树，每个节点有一个点权 aia_i，aa 是一个 1..n1 .. n 的排列。定义 f(a)f(a) 为 ai<lca(ai,aj)<aja_i < lca(a_i, a_j) < a_j 的计数，问对于所有排列，f(a)f(a) 最大为多少？

Easy Version： n≤5000n \le 5000

Hard Version： n≤1000000n \le 1000000

Easy Version 思路

Easy Version 赛时有个看着很正的猜想，最后是正确的。至于为什么正确，我也没再研究，可以参考其他文章。

首先考虑，如果树是一棵二叉树，那么对于所有节点，最优解一定是让它的左子树都大于或小于该节点，右子树则相反。显然，满足该最优构造的排列一定存在。

一般地，如果树不是一棵二叉树，那么对于所有节点，将其所有子树分成两部分，使得两部分的乘积尽可能大，即求做优的二叉树划分。这里我们需要对每个点使用背包解决，时间复杂度 O(n2)O(n^2)。

Easy Version 代码

先简单过一遍 Easy Version 代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// PermuTree (easy version)
// Module Version 230418
// Powered by GreatLiangpi
#ifdef ONLINE_JUDGE
#define TEST 1 // Test Switch
#else
// #define TEST 1
#define LOCAL 1 // Debug Switch
#endif
#ifndef LOCAL
#define TEST 1
#endif
#include <bits/stdc++.h>
#define int int64_t
#ifdef TEST
#pragma GCC optimize(3, "Ofast", "inline")  // Optimization Switch
#define endl '\n'
#endif
#ifdef LOCAL
#define endl " **\n"
#endif
#define tomax(x, y) x = max(x, (y))
#define tomin(x, y) x = min(x, (y))
using namespace std;
#ifdef TEST
const int MAX = 5005;
#else
#ifdef LOCAL
const int MAX = 105;
#endif
#endif
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1000000007;
int call_count = 0;

vector<int> edge[MAX];
int sons[MAX];
bool dp[MAX];
int res = 0;

void dfs(int x) {
    for (int y : edge[x]) {
        dfs(y);
    }
    sons[x] = 1;
    memset(dp, 0, sizeof(dp));
    dp[0] = true;
    for (int y : edge[x]) {
        sons[x] += sons[y];
        for (int j = MAX - 1; j >= sons[y]; j--) {
            if (dp[j - sons[y]]) dp[j] = true;
        }
    }
    int max_ = 0;
    for (int j = 0; j < MAX; j++) {
        if (dp[j]) {
            tomax(max_, j * (sons[x] - 1 - j));
        }
    }
    res += max_;
}

void solve() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        edge[x].push_back(i);
    }
    dfs(1);
    cout << res << endl;
}

int32_t main() {
#ifdef TEST
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false); 
#endif
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    clock_t start_time = clock();
#endif
    cout << fixed << setprecision(2);


    int t = 1;
    // cin >> t;
    while (t--)
        solve();


#ifdef LOCAL
    cout << "Used " << call_count << " Function Calls." << endl;
    cout << "Used " << (int)(clock() - start_time) << " Microseconds of Time." << endl;
#endif 
    return 0;
}

解题思路

对于 Hard Version，要求都考虑到三种优化才能得到正确的时间复杂度，时间复杂度 O(nn32)O(\frac{n\sqrt{n}}{32})。

限和背包的二进制优化

​结论： 对于一个体积为 VV 背包，如果保证所有 NN 件物品价值求和不超过 AA，可以证明使用二进制优化的时间复杂度最坏为 O(VA)O(V\sqrt{A})。

​证明： 首先考虑三个极端，物品变化对时间复杂度的影响一定介于这些极端之间。（更严谨的证明我也不会）

  • 如果背包内所有物品体积和价值均相同，二进制优化完全生效，时间复杂度为 O(Vlog⁡2min⁡(N,A))O(V\log_2{\min(N,A)})。
  • 如果背包内所有物品体积均不同，二进制优化完全失效，但这样的物品数一定不超过 2A\sqrt{2A}。因为为得到数量尽可能多的物品，所有物品价值为 11，物品体积分别为 1..x1..x，必须满足 ∑1xi≤A\sum_{1}^{x}{i} \le A。时间复杂度为 O(V2A)O(V\sqrt{2A})。
  • 如果背包内所有物品价值均不同，与上一条同理，时间复杂度为 O(V2A)O(V\sqrt{2A})。

​推论： 对于一个体积为 VV 布尔背包，如果保证所有 NN 件物品体积求和不超过 AA，使用二进制优化的时间复杂度最坏为 O(VA)O(V\sqrt{A})。

​推论： 对于一个体积为 VV 背包，如果保证所有 NN 件物品价值求和不超过 NN，使用二进制优化的时间复杂度最坏为 O(VN)O(V\sqrt{N})。

为更好隐藏题目意图，AA 的取值通常为 NN，如本题。

布尔背包的 bitset 优化

布尔背包的定义是，我们并不关心背包的最大价值，只关心背包的特定体积是否可以取到，因此布尔背包的状态转移方程为 dp[i][j]=dp[i−1][j−v[i]]  ∣  dp[i−1][j]dp[i][j]=dp[i-1][j-v[i]]~~|~~dp[i-1][j]。bitset 优化背包的时间复杂度为 O(NV32)O(\frac{NV}{32})。

待优化代码：

1
2
3
4
5
6
7
bool dp[MAX];
dp[0] = true;
for (int i = 0; i < n; i++) {
    for (int j = V; j >= v[i]; j--) {
        dp[j] |= dp[j - v[i]];
    }
}

bitset 优化：

1
2
3
4
5
bitset<MAX> dp;
dp[0] = true;
for (int i = 0; i < n; i++) {
    dp |= dp << v[i];
}

树上启发式剪枝（可证）

需要注意的是，大部分剪枝都不能对时间复杂度起到优化。但在这个问题中，将进行的优化是可证时间复杂度的。

首先我们来说明为什么必需这步剪枝。对于题目所给的背包问题的优化，我们通过上面讲到的二进制优化和 bitset 优化似乎已经可以得到正确的时间复杂度 O(nn32)O(\frac{n\sqrt{n}}{32})，但是需要注意的是，我们之前所做的优化都仅仅是对于树上一个节点的优化。我们设节点 uu 的子节点（不含孙节点）个数为 sus_u，对应背包元素个数；子孙节点个数为 tut_u，对应背包体积。则对于该节点时间复杂度为 O(tusu32)O(\frac{t_u\sqrt{s_u}}{32})，总体时间复杂度为 O(∑utusu32)O(\sum_{u}{\frac{t_u\sqrt{s_u}}{32}})，假设树为链状，依然可以达到 n2n^2。

但是为什么 Easy Version 的时间是正的

在 Easy Version 中，对于每个节点的时间复杂度为 O(tusu)O(t_us_u)，总体时间 ∑utusu≤∑unsu≤n2\sum_{u}{t_us_u} \le \sum_{u}{ns_u} \le n^2，我们当然也可以很大方的为每个节点做个体积为 nn 的背包。

考虑剪枝。因为最坏情况为链状，而对于多数情况都非常快，考虑对于每个节点，如果其最重的儿子大于等于其余儿子的求和，我们可以直接决策将最重和其余划分是最优情况。

这样做的正确性在于，对于优化后的解法，时间取决于 ∑utu\sum_{u}{t_u}，树的深度越深，∑utu\sum_{u}{t_u} 趋大。为了使树尽可能深，每个节点需拥有尽可能少的儿子，对于每个节点，最坏的情况是，拥有三个儿子，其中两个相同重，一个重量为 11，如图：

这棵树可以近似的看作一棵满二叉树，那么可以保证 ∑utu≤nlog⁡2n\sum_{u}{t_u} \le n\log_2{n}。而在 ∑utu≈nlog⁡2n\sum_{u}{t_u} \approx n\log_2{n} 的情况下，总时间复杂度 O(∑utusu32)O(\sum_{u}{\frac{t_u\sqrt{s_u}}{32}}) 中 su\sqrt{s_u} 又一定是常数级别，这与限和背包的二进制优化相似，总时间复杂度一定介于 O(nlog⁡2n32)O(\frac{n\log_2{n}}{32}) 与 O(nn32)O(\frac{n\sqrt{n}}{32}) 之间。

代码

这道题可以说很有价值吧，一道题集合了三种优化，虽然放在赛中不是很友好。

敲代码的过程也学到了一些，比如如何开动态大小的 bitset。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
// PermuTree (hard version)
// Module Version 230418
// Powered by GreatLiangpi
#ifdef ONLINE_JUDGE
#define TEST 1 // Test Switch
#else
// #define TEST 1
#define LOCAL 1 // Debug Switch
#endif
#ifndef LOCAL
#define TEST 1
#endif
#include <bits/stdc++.h>
#define int int64_t
#ifdef TEST
#pragma GCC optimize(3, "Ofast", "inline")  // Optimization Switch
#define endl '\n'
#endif
#ifdef LOCAL
#define endl " **\n"
#endif
#define tomax(x, y) x = max(x, (y))
#define tomin(x, y) x = min(x, (y))
using namespace std;
#ifdef TEST
const int MAX = 1000005;
#else
#ifdef LOCAL
const int MAX = 105;
#endif
#endif
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1000000007;
int call_count = 0;

vector<int> edge[MAX];
int sons[MAX];
int v[MAX];
bool dp[MAX];
int res = 0;

template <size_t len = 1>
void bitset_(int sons) {
    if (len < sons) {
        // 该递归仅用于动态开 bitset, 源自 cpp 的答辩语法
        bitset_<min(len * 2, (size_t)MAX)>(sons);
        return;
    }

    bitset<len + 1> dp;
    dp[0] = true;
    for (int i = 1; i <= sons; i++)
        for (int __ = 0; __ < v[i]; __++)
            dp |= dp << i;

    int max_ = 0;
    for (int i = 1; i <= sons; i++)
        if (dp[i])
            tomax(max_, i * (sons - i));

    res += max_;
}

void dfs(int x) {
    sons[x] = 1;
    if (edge[x].size() == 0) return;

    for (int y : edge[x]) {
        dfs(y);
        sons[x] += sons[y];
    }

    sort(edge[x].begin(), edge[x].end(), [&](int x, int y) -> bool {
        return sons[x] < sons[y];
    });
    int n = edge[x].size(), max_ = sons[edge[x][n - 1]];
    if (max_ * 2 >= sons[x] - 1) {
        res += max_ * (sons[x] - 1 - max_);
        return;
    }

    memset(v, 0, sizeof(int) * sons[x]);
    for (int y : edge[x]) {
        v[sons[y]]++;
    }
    for (int i = 1; i <= sons[x] - 1; i++) {
        if (v[i] > 2) {
            int delta = (v[i] - 1) / 2;
            v[i * 2] += delta;
            v[i] -= delta * 2;
        }
    }

    bitset_(sons[x] - 1);
}

void solve() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        edge[x].push_back(i);
    }
    dfs(1);
    cout << res << endl;
}

int32_t main() {
#ifdef TEST
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false); 
#endif
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    clock_t start_time = clock();
#endif
    cout << fixed << setprecision(2);


    int t = 1;
    // cin >> t;
    while (t--)
        solve();


#ifdef LOCAL
    cout << "Used " << call_count << " Function Calls." << endl;
    cout << "Used " << (int)(clock() - start_time) << " Microseconds of Time." << endl;
#endif 
    return 0;
}