专题 树形dp

1.树的难题 

solution：设f[i][j][k]为以点i为根，有j（0/1）个黑色点，k（0/1/2）个白色点的最小代价，转移方程：f[i][j + p][k + q] = min{f[i][j][k] + f[v][p][q] + len}，其中len为断掉(i,v)边的代价。

2.最佳团体

 solution：分数规划，二分一个比值mid，则第i个人的贡献为p - mid * s，以此为基础做树形dp，判断最大值能否大于0即可。

3.[HAOI2015]树上染色

 solution：随便定一个根，枚举两个端点u和v，显然，对于u内的白点，要走到v外的白点，必然通过这条边，也就是说假设u内的白点有x个，v外的白点有y个，则这条边会带来len * x * y的贡献，黑点同理，以此为基础我们树形dp。设f[i][j]为以i为根的树内有j个黑点的最大贡献，则f[u][q] = max{f[u][q - j] + f[v][j] + (j * (k - j) * e[i].len) + ((cnt[v] - j) * (n - k - (cnt[v] - j)) * e[i].len)}（内有一些细节可自行思考）。

4.临近的点

 solution：换一种思路思考，我们计算时通过父亲和儿子的累加，进行树形dp，即f[i][j] += f[v][j - 1]，以此为基础我们递推即可。

5.「JSOI2018」潜入行动

 这题推式子非常的烦。

solution：设f[i][t][j][k]为以i为根，t个装置，j（0/1）为儿子是否安放设备，k（0/1）为自己是否被监听。

直接上式子：

f[u][j + t][0][0] = (f[u][j + t][0][0] + (1ll * g[j][0][0] * f[v][t][0][1] % mod)) % mod;

f[u][j + t][1][0] = (f[u][j + t][1][0] + (1ll * g[j][1][0] * ((f[v][t][0][0] + f[v][t][0][1]) % mod)) % mod) % mod;

f[u][j + t][0][1] = (f[u][j + t][0][1] + (1ll * g[j][0][1] * ((f[v][t][0][1] + f[v][t][1][1]) % mod)) % mod) % mod;

f[u][j + t][0][1] = (f[u][j + t][0][1] + (1ll * g[j][0][0] * f[v][t][1][1]) % mod) % mod;

f[u][j + t][1][1] = (f[u][j + t][1][1] + (1ll * g[j][1][0] * ((f[v][t][1][0] + f[v][t][1][1]) % mod)) % mod) % mod;

f[u][j + t][1][1] = (f[u][j + t][1][1] + (1ll * g[j][1][1] * (((f[v][t][0][0] + f[v][t][0][1]) % mod + (f[v][t][1][0] + f[v][t][1][1]) % mod) % mod)) % mod) % mod;