前言

题目难度中等偏上，第一题的dp用记忆化搜索来做会更好思考，直接迭代维度有点多，不太好写。第二题树形dp也需要多关注规定的性质才好推导。

第一题

一家木材厂需要加工三根圆木。这三根圆木长度分别为 a,b,c，一共需要进行不超过n次加工程序。第i道加工程序需要选择其中一根长度严格大于i的圆木，将其切割，使其长度减少i。被切下的部分不再进入后续的加工流程。如果这三根圆木的长度能够组成一个面积大于0的三角形，那么就称此时的圆木长度三元组(ab,c)是好的 现在的问题是:一共可能形成多少种好的三元组?

输入描述

输入仅一行四个正整数n,a,b,c。对于100%的数据，1<=n,a,b,c<=100

输出描述

输出一行，一个整数，表示好的三元组的个数

样例输入

5 3 4 5

样例输出

10

提示

有如下10种三元组 (1,4,4),(2,2,2),(2,4,3),(2,4,5),(3,2,4),(3,3,3),(3,3,5),(3,4,2),(3,4,4),(3,4,5)

n为5即可加工不超过5次，原始3根圆木的长度为3，4，5

以(1,4,4)为例，可以第1道加工长度为5的圆木，使其长度变为4，第2道加工长度为3的圆木，使其长度变为1。此时不再进行加工，3根圆木的长度为1，4，4可以构成面积不为0的三角形

以(2,2,2)为例，可以第1道加工长度为3的圆木，使其长度变为2，第2道加工长度为4的圆木，使其长度变为2;第3道加工长度为5的圆木，使其长度变为2。此时不再进行加工，3根圆木的长度为2,2,2可以构成面积不为0的三角形

其他组合以此类推

思路与代码：

动态规划（偏暴力） 或 记忆化dfs

给出动态规划的思路和代码

定义dp[i] [j] [k] [l] 表示，第i次加工，三根木棍分别长j k l是否存在;

同时定义vis[j] [k] [l] 表示，三元组j k l是否已访问;

判断能否构成三角形可以通过两条短边之和是否大于最大边来判断；

在过程中判断能构成三角形的三元组在第一次访问时累加答案；

初始情况为dp[0] [a] [b] [c] = 1;

接下来就是循环中分别尝试对三条边做减操作；

时间复杂度O(nabc)，题目时限4s，能过

#include<bits/stdc++.h>
using namespace std;
int dp[105][105][105][105];
int vis[105][105][105];
int judge(int a, int b, int c) {
 int ma = max({a, b, c});
 if(a + b + c - ma > ma) {
  return 1;
 }
 return 0;
}
int main() {
 int n, a, b, c;
 long long ans = 0;
 cin >> n >> a >> b >> c;
 memset(dp, 0, sizeof(dp));
 memset(vis, 0, sizeof(vis));
 dp[0][a][b][c] = 1;
 if(judge(a, b, c) == 1) {
  ans++;
 }
 vis[a][b][c] = 1;
 for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= a; j++) {
   for (int k = 1; k <= b; k++) {
    for (int l = 1; l <= c; l++) {
     if(j - i > 0 && dp[i - 1][j][k][l] != 0) {
      dp[i][j - i][k][l] = dp[i - 1][j][k][l];
      if(vis[j - i][k][l] == 0 && judge(j - i, k, l) == 1) {
       ans++;
       vis[j - i][k][l] = 1;
      }
     }
     if(k - i > 0 && dp[i - 1][j][k][l] != 0) {
      dp[i][j][k - i][l] = dp[i - 1][j][k][l];
      if(vis[j][k - i][l] == 0 && judge(j, k - i, l) == 1) {
       ans++;
       vis[j][k - i][l] = 1;
      }
     }
     if(l - i > 0 && dp[i - 1][j][k][l] != 0) {
      dp[i][j][k][l - i] = dp[i - 1][j][k][l];
      if(vis[j][k][l - i] == 0 && judge(j, k, l - i) == 1) {
       ans++;
       vis[j][k][l - i] = 1;
      }
     }
    }
   }
  }
 }
 cout << ans << endl;
 return 0;
}

第二题

小明正在把玩一棵树。他正在研究树的平衡性，他为了辅助研究，为树定义了一个函数S(x)，表示对树中节点x，其到树中其他所有节点的距离之和，注意树上相邻节点之间距离为1而且树根为1号节点。现在他想让你帮他进行计算!

输入描述

第一行两个正整数n和m，分别表示树上节点数和询问数。

接下来一行n-1个数P2，P3，... ,Pn· 表示节点i的父亲为Pi。

接下来一行m个数x1，x2，xm，分别表示每次询问所使用的x值 对于所有数据，1<= n ,m<=20000，1<= pi < n，1<= xi< n

输出描述

输出一行m个数，单空格隔开，分别表示每次询问的答案

样例输入

3 3
1 1
1 2 3

样例输出

2 3 3

提示

样例图为 1是根节点，2、3节点是1号节点的子节点；

1号节点到2号节点的距离为1，到3号节点的距离为1，所以答案为2；

2号节点到1号节点的距离为1，到3号节点的距离为2，所以答案为3；

3号节点到1号节点的距离为1，到2号节点的距离为2，所以答案为3。

思路与代码：

换根dp，力扣834题的变形

首先计算根节点到其他节点的距离和

dp[u]表示以u为根的子树，其所有子节点到它的距离，nodes[u] 表示以u为根的子树的节点数量，可以得到树形dp递推式

由此dfs可得到dp[root]。

为了避免每个根都重复计算，接下来要进行换根操作

让 v 换到根u的位置，u 变为其孩子节点，同时维护原有的dp 信息，该过程中只会改变dp[u]和dp[v]，只更新这两者即可

回顾之前计算dp[]的过程，改动后，dp[u]要减去原来节点v的部分，即dp[u] -= dp[v] + nodes[v];

同时nodes也要相应减少，nodes[u] -= nodes[v];

与此同时，dp[v] 和nodes[v]也有相应的加操作

dp[v] += dp[u] + nodes[u]; nodes[v] += nodes[u];

此时就完成了换根，在O(1)时间内得到以v为根的dp值，之后就是dfs和相应的回溯操作；

本题的改动点就在于树的边的输入，以及查询，另外节点是从1开始的，代码上统一调整从0开始；

#include<bits/stdc++.h>
using namespace std;
using gg = long long;

vector<vector<gg>> map1;
vector<gg> dp, nodes, ans;

void dfs(gg u, gg fa) {
 dp[u] = 0;
 nodes[u] = 1;
 for(auto& ch : map1[u]) {
  if(ch == fa) continue;
  dfs(ch, u);
  dp[u] += dp[ch] + nodes[ch];
  nodes[u] += nodes[ch];
 }
}

void dfs2(gg u, gg fa) {
 ans[u] = dp[u];
 for(auto& ch : map1[u]) {
  if(ch == fa) continue;
  gg su = dp[u], sc = nodes[u];
  gg cu = dp[ch], cc = nodes[ch];
        
  dp[u] -= dp[ch] + nodes[ch];
  nodes[u] -= nodes[ch];
  dp[ch] += dp[u] + nodes[u];
  nodes[ch] += nodes[u];
        
  dfs2(ch, u);
  // 回溯
  dp[u] = su; nodes[u] = sc;
  dp[ch] = cu; nodes[ch] = cc;
 }
}


int main() {
 gg n, m; cin >> n >> m;
 dp.resize(n); ans.resize(n); nodes.resize(n);
 map1.resize(n, {});
 for(int i = 2; i <= n; i++) {
  gg x; cin >> x;
  gg u = i - 1, v = x - 1;
  map1[u].push_back(v);
  map1[v].push_back(u);
 }
 dfs(0, -1);
 dfs2(0, -1);
 vector<gg> pans(m);
 for(int i = 0; i < m; i++) {
  gg ask; cin >> ask;
  pans[i] = ans[ask-1];
 }
 cout << pans[0];
 for(int i = 1; i < m; i++) cout << ' ' << pans[i];
 cout << '\n'; 
 return 0;
}