#### 四、树形dp##### （一）、基础树形$dp$是在树的$dfs$中进行$dp$， 在树形$dp$中，我们动态规划的过程大概就是先递归访问所有子树，再在根上合并，我们求解的往往是所有的在子树范围内的最优解##### （二）、例题1、子树大小（1）、题意：计算每个点的子树的大小（2）、题解：状态表示：$sz[u]$代表$u$为根的子树大小状态转移：$sz[u]=1+\sum sz[v]$，

一、基础二、Bellman-Ford算法struct edge //边{int u, v;int cost;}edge[maxn];int dis[maxn], pre[maxn];//跑完Bellaman_Ford后，dis数组是从源点s到各点的最短路径，pre记录路径int n, m, s;int Bellman_Ford(){for (int i = 1; i <= n; ++i) /

一、关联容器关联容器支持高效的关键字查找和访问，两个主要的关联容器类型是map和set标准库提供以下8个关联容器：按关键字有序保存元素map关联数组：保存关键字-值对set关键字即值，只保存关键字的容器multimap关键字可重复出现的mapmultiset关键字可重复出现的set无序集合unordered_map用哈希函数组织的mapunordered_set用哈希函数组织的setu

一、关联容器关联容器支持高效的关键字查找和访问，两个主要的关联容器类型是map和set标准库提供以下8个关联容器：按关键字有序保存元素map关联数组：保存关键字-值对set关键字即值，只保存关键字的容器multimap关键字可重复出现的mapmultiset关键字可重复出现的set无序集合unordered_map用哈希函数组织的mapunordered_set用哈希函数组织的setu

一、简单语句、条件语句、迭代语句二、跳转语句1.goto语句，不建议使用，除非是跳出多重循环，使用方法如下：for (i = 0; i < n; i++){for (j = 0; j < n; j++){if (j == n - 2)goto bre;}}bre:return 0;三、try语句块和异常处理1.异常处理包括异常检测和异常处理这两部分协作，异常处理部分包括：throw表达

动态规划问题的第二个性质是子问题空间必须足够“小”，也就是说，问题的递归算法会求解相同的子问题，而不是一直生成新的子问题（分治法求解的问题在每一步递归都生成全新的子问题），由于子问题的求解依赖于更小的子问题的求解，我们将子问题的规模按大小排序，按由小至大的顺序进行求解，这样在求解某一个子问题时会依赖于上一个求解的子问题。两个问题都用到了子问题，而最长简单子路径的子问题是相关的，而最短路径的子问题是

动态规划问题的第二个性质是子问题空间必须足够“小”，也就是说，问题的递归算法会求解相同的子问题，而不是一直生成新的子问题（分治法求解的问题在每一步递归都生成全新的子问题），由于子问题的求解依赖于更小的子问题的求解，我们将子问题的规模按大小排序，按由小至大的顺序进行求解，这样在求解某一个子问题时会依赖于上一个求解的子问题。两个问题都用到了子问题，而最长简单子路径的子问题是相关的，而最短路径的子问题是