Facebook Hacker Cup 2015 Round1 40:Corporate Gifting

嘘解法で解いたらMLEして答えを提出できなかったので対策方法を書きます．公式の解法は Hacker Cup 2015 Round 1 Solutions に書いてあります．
ここでは，嘘解法の説明とスタック領域の拡張方法について説明します．
計算環境は次の通りです．

OS: Ubuntu 14.04 64bit (cat /etc/lsb-realease)
MemTotal: 3843776 kB (cat /proc/meminfo)
stack size: 8192 kB
gcc version: 4.8.2

[25 "Autocomplete"]

問題文

頂点数Nの木が与えられる．それぞれの頂点に1からNまでの値を1つ割り当てる．ただし，隣接している頂点同士は異なる値を割りつけなければならない．値を割りつけた後の各々の頂点の値の和を最小化したい．テストケースはT個ある．

$1 \le T \le 100, 1 \le N \le 2 \times 10^5$

解法

割り当てる値を色と呼ぶことにします．
この問題は一見すると頂点彩色問題（グラフ彩色 - Wikipedia）に関係がありそうに思えます．木は二部グラフなので2彩色可能となります．なので，根を1か2で塗る貪欲法で求めることが出来そうに思えますが小さいケースで反例が見つかります（公式の解法に図があります）．
ここで，func(v, c)を頂点vを根とした部分木に対して頂点vを色cで塗った場合の部分木の色の和の最小値とします．
これを，メモ化再帰で求めます．色の最大値をCとした場合の領域計算量は $O(NC)$ ，時間計算量は $O(NC^2)$ となります． $N \le 10^5$ なので大体 $C \le 30$ ぐらいだなとエスパー力を活かして嘘解法をたてます．
ただし，設定をいじらないとこの方法ではSegmentation faultとなります．

対策

Segmentation faultが起こる原因は色々あると思いますが，今回の原因はスタックオーバーフロー - Wikipedia　によるものです．メモリの種類と配置は次のサイトに書かれているようになっています．
C++マニアック,変数,local,global,variable,メモリ,memory,構築,消滅,construction,destruction,C++入門,C++言語講座
すなわちスタック領域を使い果たしてしまった為にSIGSEGVシグナルを出してプログラムが止まりました．スタックオーバーフローを回避する方法は次の通りです．

ヒープ領域を使う（グローバル変数，static変数, mallocなど）
使用できるスタック領域を増やす

スタック領域の変更方法は次の通りです（参考元：実行時スタックサイズ変更 on Linux - 日々の報告書）

# 現在のスタック領域の大きさを調べる（その他の情報も含む）
> ulimit -a
# スタック領域を16384kBに変更する
> ulimit -s 16384

実行したシェルを終了するとデフォルト値に戻ります．

ソースコード

#include <bits/stdc++.h>

using namespace std;

typedef long long  ll;

const int MAX_N = 200010;
const int MAX_C = 30;
int N, C;
int dp[MAX_N + 1][MAX_C + 1];
vector<int> tree[MAX_N];

int Rec(int v, int c)
{
    if (dp[v][c] != -1)
        return dp[v][c];

    int &res = dp[v][c];
    res = c;

    for (auto u : tree[v]) {
        int tmp = MAX_N * MAX_C;
        for (int col = 1; col <= C; ++col) {
            if (c == col)
                continue;
            tmp = min(tmp, Rec(u, col));
        }

        res += tmp;
    }

    return res;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int T, p;
    cin >> T;

    for (int i = 1; i <= T; ++i) {
        cin >> N;

        C = min(N, MAX_C);
        for (int i = 0; i < N; ++i)
            tree[i].clear();
        cin >> p;
        for (int i = 1; i < N; ++i) {
            cin >> p;
            tree[p - 1].emplace_back(i);
        }

        memset(dp, -1, sizeof(dp));

        int res = MAX_N * MAX_C;
        for (int c = 1; c <= C; ++c)
            res = min(res, Rec(0, c));

        cout << "Case #" << i << ": " << res << "\n";
    }

    return 0;
}