{\color[RGB]{255, 255, 167}{\LARGE 树上DP}}
{\color[RGB]{167, 255, 221}{\large本次的笔记大纲}}
可以根据需求学习哦
Ps:并未摘录完课上所有的例题，Typora打不动了QAQ
{\color[RGB]{167, 255, 221}{\large一道开胃小菜}}
{\large树的直径}
qwq
一看就非常的简单易懂
给你一棵树，请你求出树上最长的路径（我们称之为树的直径）。
求解方法
1.两遍 dfs 无脑跑过去
2.使用智人DP（树上DP）
方法1就不细讲了，就是从根节点搜两条链，一条最长，一条次长，这两条链的末尾结点就是树的直径的两个端点
对于方法2：
- 首先，设 dp[i][0/1] 表示第 i 点下最长链/次长链 的长度
- 然后先一路搜到子树，通过子树更新子树的父节点
- 以此类推扫到根节点，对于每个结点的 max(最长链+次长链长度)=树的直径
应该都会写了吧
{\color[RGB]{255, 255, 167}{\LARGE 换根DP}}
{\color[RGB]{169, 160, 250}{\large 定义}}
换根DP，又叫二次扫描，是树形DP的一种，其相比于一般的树形DP具有以下特点:
- 1.以树上的不同点作为根，其解不同，所以求解答案时，不能单求某节点的信息，需要求解每个节点的信息
- 2.又因为一次搜索只能得到一个节点的答案，所以我们不能通过一次搜索完成答案的求
解，而需要两次 dfs 搜索来完成求解
看起来是不是和树的直径做法很像
但是确实很像（废话）
可以康康下面的例题，试试能不能直接拍出一个做法（
{\color[RGB]{167, 255, 221}{\large例题-1}}
可以猜猜是什么难度的哦~
{\color{Violet} [USACO10MAR]}:{\color[RGB]{106,167,240} Great Cow Gathering G}
{\color{Violet} [难度评级]} :{\color[RGB]{106,167,240} [提高+/省选-] }
原题传送门--------P2986 [USACO10MAR] Great Cow Gathering G-洛谷
题目描述
Bessie 正在计划一年一度的奶牛大集会，来自全国各地的奶牛将来参加这一次集会。当然，她会选择最方便的地点来举办这次集会。
每个奶牛居住在 N 个农场中的一个，这些农场由 N-1 条道路连接，并且从任意一个
农场都能够到达另外一个农场。道路 i 连接农场 Ai 和 Bi ，长度为 Li 。集会可以在 N 个农场中的任意一个举行。另外，每个牛棚中居住着 Ci 只奶牛。
在选择集会的地点的时候， Bessie 希望最大化方便的程度 (也就是最小化不方便程度）。
比如选择第 X 个农场作为集会地点，它的不方便程度是其它牛棚中每只奶牛去参
加集会所走的路程之和
(比如，农场 i 到达农场 X 的距离是 20 ，那么总路程就是 $C[i]*20$）
请你帮助 Bessie 找出最方便的地点来举行大集会
输入输出样例
输入 #1
5 1 1 0 0 2 1 3 1 2 3 2 3 4 3 4 5 3
输出 #1
15
1≤N≤10^5，1≤Ai≤Bi≤N，0≤Ci,Li≤10^3。
下面就是解法了
可以仔细想想看再往下翻哦
{\color[RGB]{199, 245, 255}{\large解法：}}
首先考虑枚举聚会点， dfs 搜索，复杂度 n^2 ，直接爆炸（
我们再仔细观察、发现一下性质：
对于聚会点的移动，我们在改变聚会点时，比如说是这样一张图：
假设他们都前往 1 结点进行聚会（红色箭头是前往的路径）
在计算出值后，再更换聚会结点至3结点。
我们发现，不需要重新 dfs 计算一遍值，我们只要把 3 子树内的点往 3 退一步，而非 3 子树内的点往 3 前进一步。
具体到答案的计算，我们假设在 1 号点聚会所花费的总不方便值为 ans , 1 \to 3 之间边权为 w ,第 i 的奶牛数量为 Ci ,所以当 1 转移到 3 时 ans-(C[5]+C[4])*w+(C[1]+C[2])*w
这样就结束喽
当然也可以康康洛谷上的题解，或许对代码实现更有帮助qwq
{\color[RGB]{255, 255, 167}{\LARGE 树上背包}}
{\color[RGB]{167, 255, 221}{\large一道模板（水）题}}
真的是水题吗
题目描述
公司的人际关系构成一棵树，现公司要举行一场晚会并规定:如果邀请了某个人那么一定不会邀请他的上司(上司的上司，上司的上司的上司.(都可以邀请)每个人都有一个气氛值，求一个邀请方案，使气氛值的和最大)
数据规模：(n表示公司的人数)
1<=N<=100000
根据题面越短，题目越难理论！
这道题！一定是…
是什么题呢？去luogu搜索:"没有上司的舞会"即可知道答案（忘记贴链接了 我背个锅）
下面就是题解，其实蛮好想的（逃
{\color[RGB]{199, 245, 255}{\large解法：}}
f[i][1/0] 表示在第 i 点时 是/否 取本点时获得的最大气氛值
若这里是 f[i][1] 表示取本点，在向父节点转移时转移到 f[fa][0] ,不能转移到 f[fa][1]
（原因见状态定义+题面 取了子节点就不能取本点了！）
而若现在从 fa 遍历到了 i ，那么对于 i 的父节点 fa :
f[fa][1]=f[fa][1]+f[i][0]
f[fa][0]=f[fa][0]+max(f[i][0],f[i][1])
{\color[RGB]{167, 255, 221}{\large一道例题}}
{\color{Violet} [NOI2002]}:{\color[RGB]{106,167,240} 贪吃的九头龙 }
{\color{Violet} [难度评级]} :{\color[RGB]{106,167,240} [提高+/省选-] }
原题传送门--------P4362 [NOI2002] 贪吃的九头龙 - 洛谷
↑这次可没忘记原题链接奥
{\color[RGB]{167, 255, 221}{\large题面：}}
有一条九头龙有 m 个脑袋(我也不知道为什么九头龙有 m 个脑袋)，给出一棵树，n个结点，每个结点上都有一个果子，对于兄弟结点，若都被同一个脑袋吃掉，则会产生1的难受值。
这 m 个脑袋中有 1 个最大，对于最大的一个脑袋，给出限制，它必须恰好吃 k 个果子，问难受值最小是多少？
{\color[RGB]{167, 255, 221}{\large数据范围：}}
1<=n<=300 ， 2<=m<=n ， 1<=k<=n
啊啊啊真的可以做吗！！！！！！！
是 可以的（doge
{\color[RGB]{199, 245, 255}{\large解法：}}
头的个数与向上传递信息的算法有关.两种情况：
{\color[RGB]{199, 245, 255}{\large Case\ 1:}}
头个数大于2，小头需要吃的果子，可由两个小头共同完成，所以只考虑大头的情况
{\color[RGB]{199, 245, 255}{\large Case\ 2:}}
头个数等于2，既要考虑大头的难受值，又要考虑小头的难受值.
{\color[RGB]{199, 245, 255}{\large 定义状态\ :}}
F[i,j] 表示以 i 为根的树，大头吃 j 个果实的最小难受值.
转移时需要知道它的子树的根是否是大头所吃.所以增加半维
定义状态 f[i,j,k] 表示以 i 为根的树，大头吃 j 个果子的最小难受值.
K=0 表示大头不吃根节点， K=1 表示大头吃根节点。
{\color[RGB]{199, 245, 255}{\large 状态转移\ :}}
( v 是 i 的一个儿子， temp 为上一次转移完后的 f 值， w[i][j] 为 (i,j) 这条边的难受值)
F[i][j][1]=min({f[v][k][1]+temp[i][j-k][1]+w[i][v],f[v][k][0]+temp[i][j-k][1]});
(0<=k<j) ↑
F[i][j][0]=min({f[v][k][1]+temp[i][j-k][0],f[v][k][0]+temp[i][j-k][0]+w[i][v](m=2)})
F[i][j][0]=min({f[v][k][1]+temp[i][j-k][0],f[v][k][0]+temp[i][j-k][0](m!=2)})(0<=k<=j) ↑ ↑
感觉如何（
{\color[RGB]{255, 255, 167}{\LARGE 再来一道例题}}
要是大脑冒烟了可以在下面休息一会
给定一棵树n， n\le1e6 ,求出 \oplus 异或和最大的路径
{\color[RGB]{199, 245, 255}{\large解法：}}
直接拍一个01Trie，01Trie就是专门维护这一类最大异或和问题的（惯犯
不知道01Trie的可以去看看 【学习笔记】带你从0开始学习 01Trie - TheSky233 - 博客园 (cnblogs.com)
↑ 上图笔记截图来自dalao@洪宇帆
已知上图笔记中错误：
1、第三个点中的“异或”打成了“疑惑”
2、程序第4行的 if 后 T[rt][(v>>1)\&1]=++cnt; 应改为 T[rt][(v>>i)\&1]=++cnt;
以上
就是本次所有的内容啦
上课做笔记做得要裂开了
后来又去补了一些内容
方便的话能点个赞支持一下吗
整理这么多真的很不容易QAQ
对了
笔记中有误记得和我说一声 会去更改的qwq
看完了可以留言说说感受，每一条都会看！
