算法笔记之树形DP——路径相关DP、树的着色以及树的最大独立集问题

路径相关DP——树的路径最大权值问题

问题本身比较容易理解，就是在一棵树上任取两个点，计算这两个点所形成的路径权值（可以是端点的权值，也可以是边的权值），重复操作多次，使整棵树的权值最大。

来看蓝桥上的一道题：https://www.lanqiao.cn/problems/3649/learning/?page=1&first_category_id=1&name=%E6%9C%80%E9%95%BF%E4%B9%98%E7%A7%AF%E9%93%BE

结合样例理解题意之后，我们发现有一点非常重要，那就是选取的两条路径不可以有公共边。这要落实到代码上要怎么做呢？

对于某一点i，我们设从它出发向下走的路径为path_down，向上走的路径为path_up。假设我们先形成了path_down，那么之后在形成path_up的过程中遇到的每一个端点v我们都要判断下它是否曾经出现在了path_down中。而path_down是向下最长的一条路径，因此我们可以总结说：

在形成向上最长路径的过程中，遇到的每一个端点，都要判断它是不是向下最长路径的端点。

如果不是，那我们当然可以欣然接受它成为path_up的一员了。那如果不是呢？我们就需要再记录一条方向向下的、路径次长的路径path2_down，在这条向下的路径中不会存在path_down中的端点。我们将它纳入到path_up当中，既不会和path_down有重合，也可以使得权值尽可能大。

我们用图来表示或许更加直观。这是情况1：当端点v1不在path1_down中，我们就可以考虑将path1_down纳入到path_up当中，不要搞乱了，这里说的path1_down是父节点的，所以对于v1而言，路径方向还是向上的。

path_up[v1]=edge_weight+max(path_up[u],path1_down[u]);

情况2：当端点v1已经是path1_down中的一员了，我们就不可以再取path1_down了，这时候考虑次长路径path2_down。

path_up[v1]=edge_weight+max(path_up[u],path2_down[u]);

根据以上的分析，我们定义了如下5个数组：

path1_down[N];//path1_down[i]表示根节点为i的、方向向下的最长路径权值
path2_down[N];//path2_down[i]表示根节点为i的，方向向下的次长路径权值
p1_down[N];//p1_down[i]表示根节点为i的，在最长路径中的下一个子节点
p2_down[N];//p2_down[i]表示根节点为i的，在次长路径中的下一个子节点
path_up[N];//path_up[i]表示根节点为i的，方向向上的最长路径权值

为了构建向下和向上两个方向的路径，我们应当分别写出对应的DFS：

//vector> tree[N];
//cin>>a>>b>>c;
//tree[a].push_back({b,c});
//tree[b].push_back({a,c});
//v.first是下一个子节点，v.second是边的权重
void DFS1(int u,int fa){
   for(auto v:tree[u]){
     if(v.first==fa)continue;
     DFS1(v.first,u);
     if(path1_down[v.first]+v.second>=path1_down[u]){
        path2_down[u]=path1_down[u];//更新次长距离
        p2_down[u]=p1_down1[u];//更新次长距离的最近子节点
        path1_down[u]=path1_down[v.first]+v.second;
        p1_down[u]=v.first;
     }else if(path1_down[v.first]+v.second>path2_down[u]){
        path2_down[u]=path1_down[v.first]+v.second;
        p2_down[u]=v.first;
     }
   }
}
void DFS2(int u,int fa){
    for(auto v:tree[u]){
       if(v.first==fa)continue;
       if(v.first==p1_down[u]){
          path_up[v.first]=v.second+max(path_up[u],path2_down[u]);
       }else{
          path_up[v.first]=v.second+max(path_up[u],path1_down[u]);
       }
     DFS2(v.first,u);
   }
}

DFS1和DFS2分别做完后，对每个结点分别计算一次最长乘积链，就可以得出正确答案了。上面没有提到的是，最长乘积链中的两条路径，当然可以都是方向向下的，这个容易理解，不多说。

ll ans=0;
for(int i=1;i<=n;i++){
    ans=max(ans,max(1LL*path_up[i]*path1_down[i],1LL*path1_down[i]*path2_down[i]));
}

这一题也是类似的思想，只不过我们仍然可以设置权重，且权重都为1：https://www.lanqiao.cn/problems/4329/learning/?page=1&first_category_id=1&name=%E6%A0%91%E7%9A%84%E8%BF%9E%E8%BE%B9

着色方案数——树的着色问题

有关涂色的问题，想必我们在高中就有接触了，其问题的核心就是局部不同位置方案数的相乘，得出整体涂色的方案总数。知道了这个，DP数组的定义就好写了：

int dp[N][2];
//dp[i][0]:将节点染色为0时，根节点为i的树的合理方案数
//dp[i][1]:将节点染色为1时，根节点为i的树的合理方案数

如果给本题做一个小小的限制，即相邻的两个节点（即有一条边直接相连的节点）不能都被染成颜色1。就像蓝桥上这一道题：https://www.lanqiao.cn/problems/5209/learning/?page=1&first_category_id=1&name=%E6%A0%91%E7%9A%84%E7%9D%80%E8%89%B2

那我们可以分析：对于每一个以i为根节点的树，我们要么对这个节点涂色为0，要么为1。

若为0，则其子树v涂色为0或为1都可以，也就是说每一棵子树的方案数都是(dp[v][0]+dp[v][1])

若为1，则其子树v只能涂色为0，也就是说每一棵子树的方案数都是dp[v][0]

很容易地写出递推公式:

dp[u][0]=(dp[u][0](dp[v][0]+dp[v][1]))%mod;
dp[u][1]=(dp[u][1]dp[v][0])%mod;

典型的由小化大——树的最大独立集

树的独立集：选出树中尽量多的点，使得任何两个节点均不相邻，输出一个最大独立集。

上面那道题会做了，这道题也是很简单的。对于每一棵以i为根节点的树，要么选，要么不选。

int dp[N][2];
//dp[i][0]:不选节点i时，根节点为i的树的最大独立集的大小
//dp[i][1]:选了节点i时，根节点为i的树的最大独立集的大小

不选，那么这棵的树的最大独立集就由它的所有子树来决定dp[u][0]+=max(dp[v][0],dp[v][1]);。

选了，就只能取不选子树情况下的最大独立集dp[u][1]+=dp[v][0];

值得注意的是，与上一题不同的是本地不再是方案数相乘，而是明确的一个个子集的相加，汇集成了整棵树的最大独立集。