///**//低落...
最近做了以及看了树形dp这部分的知识，感觉有必要做一些整理，所以特来此地写下来。我将整理一些树形dp基本的模板与应用以及思想。
1.树的直径：树上最长的链
概念应该很好懂，那么现在来看看代码（简略版）：
#include<iostream>
using namespace std;
struct EDGE{
int u,v,l;
EDGE* ne;
}edge[1000010];
struct NODE{
EDGE* fir;
}node[1000010];
//...省略加边的函数
int ans;
void dfs(int u){
vis[u]=1;//注意标记，为了不走父节点一遍；
int d1=0,d2=0;
EDGE* i=node[u].fir;
while(i!=NULL){
if(vis[i->v])continue;//如果没有标记，可能会往上走，这样就死循环了。
int d=i->l+dfs(i->v);
if(d>d1){
d2=d1;
d1=d;
}else if(d>d2){
d2=d;
}
i=i->ne;
}
ans=max(ans,d1+d2);//最后的ans就是树的直径
return d1;//返回的是此节点发出的最长链。
}
int main()
{
//...略
}
我没有写加边等基础操作。但是写了终点：dfs
求树的直径的重点就在于求这个dfs。
（第一次画图，好丑。。。）
比如看这个图，我们发现对于每个节点（除了叶子节点哈...）它所对应的最长链就是它的子树中的最长链和次长链的和。橙色节点的最长链是橙色的线，黄色节点对应的最长链是黄色的线。我们进一步发现，父节点的最长链就是有它发出的两条最长和次长的链。那么可以感觉到，我们对于一个节点要维护它的两个信息：最长链和次长链。然后从叶子到根递归（也就是先dfs后计算）。走一遍树就可以得到最终的结果了。
来砍一刀树的直径的题目~：
这题看上去是个博弈论，但其实用到了树的直径。（在此只简略说明哪里用到，不回答整个问题）。我们要判断2*r1+1与直径的大小关系。如果直径相比小点，那么一定会炸死。（其实也用到了树的中心趋于直径中点）；
2.树的中心：给定一颗树，请在树上找一个点，该点到树中其他点的最远距离最近，该点称为树的 中心。
暴力做法：遍历每个节点，每个节点dfs一遍求此点到树中其它点的距离，最后求到最小值即可。 这样肯定会T掉。。。
思考：我们搜索树，肯定是以一个节点为根节点这样搜索。不妨就令1号节点为根节点，这样我们就是从上往下走一遍了。这样走一遍我们可以利用dfs从叶子到根递归一遍，求出每个节点到其叶子节点的最远距离，即为“向下”走的最远距离。但别忘了还有它的根节点没有考虑！！！所以我们还需要再开一个dfs从根到叶子遍历，求出其“向上”走的最远距离。这样就开两个数组，一个d数组记录每个点向下的最远距离，一个up数组记录向上的最远距离。两者max就是答案！
这里提一嘴：如果从叶子节点到根节点递归，其实就是先dfs后求值。因为要等到把叶子节点的信息都算完才能处理根节点。而从根节点到叶子节点递归，就是先求值再dfs。因为叶子节点要用到根节点的信息，所以要先处理完根节点才能处理叶子节点。
下面来看一下模板~
struct EDGE{
int u,v,l;
EDGE* ne;
}edge[1000010];
struct NODE{
EDGE* fir;
}node[1000010];
int up[1000010],d1[1000010],d2[1000010],dd1[1000010];//dd1用来标记每个点向下走的最长路径的子节点
int dfs1(int u,int fa){
//由叶子到根跑dfs，先dfs再计算，最后要返回值（虽然也是从根开始跑，但只有最后走到叶子才会停止并返回。所以相当于从叶子到根跑）
d1[u]=0;d2[u]=0;
EDGE* i=node[u].fir;
while(i!=NULL){
if(i->v==fa)continue;
int L=i->l+dfs(i->v,u);
if(d1[u]<L){
dd1[u]=i->v;
d2[u]=d1[u];
d1[u]=L;
}else if(d2[u]<L){
d2[u]=L;
}
i=i->ne;
}
return d1[u];
}
void dfs2(int u,int fa){//up不需要初始化为0；
//从根到叶子跑dfs，先把u的f算好再dfs。同理每部dfs算好子节点的答案，再从子节点开始dfs。
EDGE* i=node[u].fir;
while(i!=NULL){//要筛选向下的吗？
if(i->v==fa)continue;
int L=i->l+dfs2(i->v,u);
if(dd1[u]==i->v){
up[i->v]=i->l+max(up[u],d2[u]);//注意这里改的是i的up，而不是u的；
}else{
up[i->v]=i->l+max(up[u],d1[u]);
}
dfs(i->v,u);//深搜u的子节点i
i=i->ne;
}
}
int main()
{
//...
dfs1(1,-1);
dfs2(1,-1);
for(int i=1;i<=n;i++){
ans=min(ans,max(up[i],d[u]));
}
//...
}
小小的归纳：为什么树的直径和树的中心，一个要用两遍dfs，一个只要用一遍呢？那么我们遇到题目如何判断用两遍还是一遍呢？
//Attention:虽然这题建图是建双向图，可能会疑惑那么跑的时候不就没有根和叶子了吗？其实不是。跑第一遍dfs时会标记父亲节点，相当于人为加上了父亲节点。这样子如果要实现子节点向上查询的操作就会很难下手。所以要跑两遍dfs。第一遍dfs从下向上得结果，第二遍dfs从上向下得结果。可以总结理解为，只要需要所有节点向所有方向都要走，就要有两遍dfs。所以可以知道：树的直径只要向下维护，但不要向上维护；但树的中心既要维护下面又要得到上面，所以dfs数量自然不同。
3.例题：积蓄程度
有一个树形的水系，由 N−1N−1 条河道和 NN 个交叉点组成。
我们可以把交叉点看作树中的节点，编号为 1∼N1∼N，河道则看作树中的无向边。
每条河道都有一个容量，连接 xx 与 yy 的河道的容量记为 c(x,y)c(x,y)。
河道中单位时间流过的水量不能超过河道的容量。
有一个节点是整个水系的发源地，可以源源不断地流出水，我们称之为源点。
除了源点之外，树中所有度数为 11 的节点都是入海口，可以吸收无限多的水，我们称之为汇点。
也就是说，水系中的水从源点出发，沿着每条河道，最终流向各个汇点。
在整个水系稳定时，每条河道中的水都以单位时间固定的水量流向固定的方向。
除源点和汇点之外，其余各点不贮存水，也就是流入该点的河道水量之和等于从该点流出的河道水量之和。
整个水系的流量就定义为源点单位时间发出的水量。
在流量不超过河道容量的前提下，求哪个点作为源点时，整个水系的流量最大，输出这个最大值。
输入格式
输入第一行包含整数 TT，表示共有 TT 组测试数据。
每组测试数据，第一行包含整数 NN。
接下来 N−1N−1 行，每行包含三个整数 x,y,zx,y,z，表示 x，yx，y 之间存在河道，且河道容量为 zz。
节点编号从 11 开始。
输出格式
每组数据输出一个结果，每个结果占一行。
数据保证结果不超过 231−1231−1。
数据范围
N≤2×105N≤2×105
输入样例：
1
5
1 2 11
1 4 13
3 4 5
4 5 10
输出样例：
26思考：其实这题就是求每个点出发到其子树的最大流量。那么我们自然用树形dp dfs来维护。这时候用几遍dfs呢？我们发现一个节点不仅要维护它的子树，还要维护它向上的部分。那么就是用两遍dfs来解决~
看一下代码~
//Attention:虽然这题建图是建双向图，可能会疑惑那么跑的时候不就没有根和叶子了吗？其实不是。跑第一遍dfs时会标记父亲节点，相当于人为加上了父亲节点。这样子如果要实现子节点向上查询
//的操作就会很难下手。所以要跑两遍dfs。第一遍dfs从下向上得结果，第二遍dfs从上向下得结果。可以总结理解为，只要需要所有节点向所有方向都要走，就要有两遍dfs
struct EDGE{
int u,v,l;
EDGE* ne;
}edge[1000010];
struct NODE{
EDGE* fir;
}node[1000010];
int up[1000010],d1[1000010],d2[1000010],dd1[1000010];//dd1用来标记每个点向下走的最长路径的子节点
int dfs1(int u,int fa){
//由叶子到根跑dfs，先dfs再计算，最后要返回值（虽然也是从根开始跑，但只有最后走到叶子才会停止并返回。所以相当于从叶子到根跑）
d1[u]=0;d2[u]=0;
EDGE* i=node[u].fir;
while(i!=NULL){
if(i->v==fa)continue;
int L=i->l+dfs(i->v,u);
if(d1[u]<L){
dd1[u]=i->v;
d2[u]=d1[u];
d1[u]=L;
}else if(d2[u]<L){
d2[u]=L;
}
i=i->ne;
}
return d1[u];
}
void dfs2(int u,int fa){//up不需要初始化为0；
//从根到叶子跑dfs，先把u的f算好再dfs。同理每部dfs算好子节点的答案，再从子节点开始dfs。
EDGE* i=node[u].fir;
while(i!=NULL){//要筛选向下的吗？
if(i->v==fa)continue;
int L=i->l+dfs2(i->v,u);
if(dd1[u]==i->v){
up[i->v]=i->l+max(up[u],d2[u]);//注意这里改的是i的up，而不是u的；
}else{
up[i->v]=i->l+max(up[u],d1[u]);
}
dfs(i->v,u);//深搜u的子节点i
i=i->ne;
}
}
int main()
{
//...
dfs1(1,-1);
dfs2(1,-1);
for(int i=1;i<=n;i++){
ans=min(ans,max(up[i],d[u]));
}
//...
}
以上就是最近遇到的树形dp类题目，以后遇到还会更新滴！~
标签：题型,int,up,dfs,dp,d2,节点,模板,d1 From： https://blog.csdn.net/2301_81888203/article/details/141634120