AC代碼：

https://codeforces.com/contest/1778/submission/201757333

題意：

已知一個(gè)有根的樹(shù)，由n個(gè)從1到n編號(hào)的頂點(diǎn)組成。頂點(diǎn)1是樹(shù)的根。每個(gè)頂點(diǎn)都有一個(gè)整數(shù)值。第i個(gè)頂點(diǎn)的值是ai。您最多可以執(zhí)行以下操作k次。

選擇一個(gè)以前沒(méi)有選擇過(guò)的頂點(diǎn)v和一個(gè)整數(shù)x，使得x是v的子樹(shù)中所有頂點(diǎn)值的公約數(shù)。

v子樹(shù)中每個(gè)頂點(diǎn)的值乘以x。

在最多k次操作之后，根節(jié)點(diǎn)1的最大可能值是多少？從形式上講，您必須使a1的值最大化。

題解：

樹(shù)形DP