考察

人間のやる気はつねに \(0\) 以上なので、次のように問題文を言い換えてもよいです：

\(m\) 冊の冊子を、部下がいない人間たちに配る。その後、各人間が冊子を持っていたら、その上司（委員長以外は必ず \(1\) 人存在する）に渡す。最終的には委員長に再び \(m\) 冊返ってくることになる。

そうすると、もとの問題で「部下を \(1\) 人選んで冊子を渡す」という操作が必要なくなり、見通しが少しよくなります。

次の動的計画法を考えます。

\(dp[i][j]\) : 人間 \(i\) とその部下に冊子が合計 \(j\) 冊渡されたとき、「\(i\) とその部下たち」の中で冊子を渡された人間のやる気の合計の最大値

このとき、 \(i\) の部下を \(s_1, s_2, \cdots, s_k\) とすると、

\[ dp[i][j] = \begin{cases} \displaystyle a_i + \max_{x_1 + x_2 + \cdots + x_k = j}\left(\sum_{i=1}^k dp[s_i][x_i]\right) & (j \ge 1)\\ 0 & (j = 0) \end{cases} \]

が成り立ちます。ただし, \(\displaystyle \max_{x_1 + x_2 + \cdots + x_k = j}\) とは、\(x_1 + x_2 + \cdots + x_k = j\) となるような非負整数の \((x_1, x_2, \cdots, x_k)\) のすべて対して \(\max\) を取ることを意味します。

これは、 \((\max, +)\) 畳み込みであり、\(dp[s_1], dp[s_2], \cdots, dp[s_k]\) を順にマージする（畳み込む）ことで得られます。

\(j \le M\) だけを考えればよいので、各マージにおいて計算量は \(O(M^2)\) となります。マージ回数は \(N\) 回以下なので、時間計算量 \(O(NM^2)\) で問題に答えることができます。

しかし、このままでは低速で間に合いません。

高速化

委員長が部下を持たない人間に渡す冊子の数は高々 \(1\) 冊でよいです。

よって、 \(i\) が持ちうる冊子の冊数は、「 \(i\) とその部下の人数の合計」以下です。したがって、 \(dp[i][j]\) における \(j\) は、「\(i\) とその部下の人数の合計」と \(M\) との小さい方以下だけを考えればよいことになります。

とくに、部下を持たない人間 \(i\) については \(dp[i][0] = 0, dp[i][1] = a_i\) だけを保持すればよいです。

そうすると、実は DP 全体で時間計算量が \(O(NM)\) で抑えられ、実行時間制限に間に合います。

これは \(O(NK)\) の木 DP と呼ばれているテクニックです。本問題において \(M\) に制限がない場合も \(O(N^2)\) で解くことができ、こちらは 二乗の木DP と呼ばれています。

詳しい計算量解析は以下の記事が参考になります。

木と計算量 前編 〜O(N^2)とO(NK)の木DP〜 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

以下は実装例です。

実装例(C++)