[Idea] Using HLD to reduce memory

Revision en3, by maomao90, 2023-03-03 07:11:07

Recently when I was doing Universal Cup Round 5, I got stuck a tree problem A as I realised that my solution required way too much memory. However, after the contest, I realised that there was a way that I can reduce a lot of memory using HLD. So here I am with my idea...

Structure of Tree DP

Most tree DP problems follow the following structure.

struct S {
    // return value of DP
};
S init(int u) {
    // initialise the base state of dp[u]
}
S merge(S left, S right) {
    // returns the new dp state where old state is left and transition using right
}
S dp(int u, int p) {
    S res = init(u);
    for (int v : adj[u]) {
        if (v == p) continue;
        res = merge(res, dp(v, u));
    }
    return res;
}
int main() {
    dp(1, -1);
}

An example of a tree DP using this structure is maximum independent set (MIS).

Code

Suppose struct $$$S$$$ requires $$$|S|$$$ bytes and our tree has N vertices. Then this naive implementation of tree dp requires $$$O(N\cdot |S|)$$$ memory as res of the parent is stored in the recursion stack as we recurse down to the leaves. This is fine for many problems as most of the time, $$$|S| = O(1)$$$, however in the case of the above question, $$$|S| = 25^2\cdot 24$$$ bytes and $$$N = 10^5$$$, which will require around $$$1.5$$$ gigabytes of memory, which is too much to pass the memory limit of $$$256$$$ megabytes.

Optimization

We try to make use of the idea of HLD and visit the visit the vertex with the largest subtree size first.

struct S {
    // return value of DP
    int take, notTake;
};
S init(int u) {
    // initialise the base state of dp[u]
    return {1, 0};
}
S merge(S left, S right) {
    // returns the new dp state where old state is left and transition using right
    return {left.take + right.notTake, left.notTake + max(right.take, right.notTake)};
}
int sub[MAXN];
void getSub(int u, int p) {
    sub[u] = 1;
    pair<int, int> heavy = {-1, -1};
    for (int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        if (v == p) continue;
        heavy = max(heavy, {sub[v], i});
    }
    // make the vertex with the largest subtree size the first
    if (heavy.first != -1) {
        swap(adj[u][0], adj[u][heavy.second]);
    }
}
S dp(int u, int p) {
    // do not initialize yet
    S res;
    bool hasInit = false;
    for (int v : adj[u]) {
        if (v == p) continue;
        if (!hasInit) {
            res = init();
            hasInit = true;
        }
        res = merge(res, dp(v, u));
    }
    if (!hasInit) {
        res = init();
        hasInit = true;
    }
    return res;
}
int main() {
    getSub(1, -1);
    dp(1, -1);
}
Tags hld, memory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English maomao90 2024-04-07 12:31:56 126 Tiny change: '.\n\n[cut]\n\n# Opti' -> '.\n\n[cut] \n\n# Opti'
en9 English maomao90 2023-03-04 03:27:10 27 Tiny change: '\n ' -> '\n sub[u] += sub[v];\n '
en8 English maomao90 2023-03-03 13:23:19 23 Tiny change: '\n ' -> '\n getSub(v, u);\n '
en7 English maomao90 2023-03-03 09:50:46 21
en6 English maomao90 2023-03-03 09:32:29 36
en5 English maomao90 2023-03-03 07:51:24 1506 (published)
en4 English maomao90 2023-03-03 07:12:35 132
en3 English maomao90 2023-03-03 07:11:07 3083 Tiny change: 'uires $O(N|S|)$ memo' -> 'uires $O(N\cdot |S|)$ memo'
en2 English maomao90 2023-03-02 19:01:59 153
en1 English maomao90 2023-03-02 19:00:27 222 Initial revision (saved to drafts)