树形dp解法

二叉树的直径

将一棵树抽象成左子树,右子树,根节点,求出左子树作为根的最长链长度l,右子树作为根的最长链长度r,则其父节点的最长链长度为max(l,r)+1

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans=0;
    int dfs(TreeNode*node)//返回以当前节点为根的最长链
    {
        if(node==nullptr)
        return -1;
        int l_len=dfs(node->left);
        int r_len=dfs(node->right);
        ans=max(ans,l_len+r_len+2);
        return max(l_len,r_len)+1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

最大路径和

也是求出左右子树的最大路径和lsum,和rsum,而父节点的最大路径和就为max(lsum,rsum)+node->val,而空节点返回0.还有一点要注意的是如果父节点求出的最大路径和为负数,那他对最终的总和的贡献为负,可以直接不选,返回0即可

class Solution {
public:
    int ans=-1000000000;
    int dfs(TreeNode*node)
    {
        if(node==nullptr)
            return 0;
        int lsum=dfs(node->left);
        int rsum=dfs(node->right);
        ans=max(ans,lsum+rsum+node->val);
        return max(max(lsum,rsum)+node->val,0);
    }
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

打家劫舍3

这题可分偷根节点和不偷根节点两种情况,如果偷根节点,那它的两个儿子都不能偷,如果不偷根节点,那它的两个儿子偷与不偷均可

class Solution {
public:
    pair<int,int> dfs(TreeNode*node)
    {
        if(node==nullptr)
        return {0,0};
        auto[lrob,lnrob]=dfs(node->left);
        auto[rrob,rnrob]=dfs(node->right);
        int rob=lnrob+rnrob+node->val;
        int nrob=max(lnrob,lrob)+max(rnrob,rrob);
        return {rob,nrob};
    }
    int rob(TreeNode* root) {
        auto[l,r]=dfs(root);
        return max(l,r);
    }
};

相邻字符不同的最长路径

class Solution {
public:
    int ans=0;
    vector<int>g[100005];
    int dfs(int x,int pr,string&s)
    {
        int maxlen=0;
        for(auto y:g[x])
        {
            if(y==pr)continue;
            int len=dfs(y,x,s)+1;
            if(s[y]!=s[x])
            {
                ans=max(ans,maxlen+len);
                maxlen=max(maxlen,len);
            }
        }
        return maxlen;
    }
    int longestPath(vector<int>& parent, string s) {
        int n=parent.size();
        for(int i=1;i<n;i++)
        {
            g[parent[i]].push_back(i);
            g[i].push_back(parent[i]);
        }
        dfs(0,-1,s);
        return ans+1;
    }
};

没有上司的舞会

这题是打家劫舍3的升级版,不再是二叉树,而是一般的树,要做这一题,你得先学会建树,你可以采用建图的的方法建树(邻接表法),然后你要了解树形dp的基本模版,这个题与打家劫舍的思路一样,不同的是,一个节点可能有多个儿子,根节点不选=求和(max(儿子选,儿子不选)),根节点选=求和(儿子不选),你可以用一个vector保留本层的儿子的结果,再根据儿子的结果,求出当且节点(父节点)的结果,再return

#include<bits/stdc++.h>//选=求和(不选) 不选等于求和(max(选,不选))
using namespace std;
#define int long long
vector<int>g[6005];//邻接表储存树
pair<int,int>dfs(int x,int pr,vector<int>&v)
{
    vector<pair<int,int>>que;
    for(auto i:g[x])
    {
        if(i==pr)continue;//遍历到父节点,跳过此次循环
        pair<int,int>p=dfs(i,x,v);//得到每个儿子选和不选的结果
        que.push_back(p);
    }
    int rob=0,nrob=0;
    for(int i=0;i<que.size();i++)
    {
        rob+=que[i].second;//子树不选,选根
        nrob+=max(que[i].first,que[i].second);
    }
    rob+=v[x];//得到当前节点选和不选的结果
    return{rob,nrob};//返回当前结果
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,l,k;
    cin>>n;
    vector<int>v(n+1);//快乐指数
    for(int i=1;i<=n;i++)cin>>v[i];
    for(int i=0;i<n-1;i++)//建树
    {
        cin>>l>>k;
        g[l].push_back(k);
        g[k].push_back(l);
    }
    auto[lrob,rrob]=dfs(1,-1,v);//求得根节点选和不选的情况
    cout<<max(lrob,rrob);//输出结果
    return 0;
}