2019暑期集训第六讲：动态规划(I)

动态规划（线性，区间，树形）

对于动态规划 我们所需要确定的肯定就是以下几种元素

  1. 状态（阶段）

我们确定的状态要保证当前的状态不会对于后面的状态产生影响 这个条件也被叫做无后效性 并且这个状态能够表示出所有的状态

​ 2.决策

我们利用什么样的决策从前面一个阶段转移到我当前的阶段过来（可能是前面的阶段去最小值，最大值之类的）

开始写代码的时候要确定状态的起始条件（也就是边界条件） 再确定状态的最总目标 （也就是我们要求的答案）

1.线性dp

具有线性“阶段”划分的动态规划算法被称为线性dp

题目 1：

给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为1 * 1或更大的连续子阵列。矩形的总和是该矩形中所有元素的总和。在这个问题中，具有最大和的子矩形被称为最大子矩形。例如，下列数组：

0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 其最大子矩形为：

9 2 -4 1 -1 8 它拥有最大和15

对于这个问题 我们当然可以直接暴力枚举这个区间的起始端点和结束端点来求答案，但是这个方案的复杂度太高了，我们可以想到之前做过的最大的连续子序列和的线性dp来解这道题目 这道题目只不过是扩大到了二维而已；

解题思路：我们假设把每一行和看做一个新的元素 然后就是二维的降到了一维的 然后在跑一次一维的连续子序列dp 更新一下答案就好了

具体代码如下

#include<bits/stdc++.h>

using namespace std;

int a[102][102],sum[102][102],dp[102];

int main()
{
    int n;
    cin>>n;
    memset(sum,0,sizeof(sum));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            cin>>a[i][j];
            sum[i][j] = sum[i][j-1] + a[i][j];// 每一行都当做一个元素
        }
    }
    int ans = -1000;
    for(int j = 1; j <= n ; j++)
    {
        for(int k = 0; k < j; k++)// 这两个for循环枚举区间的左右端点
        {
            for(int p = 0; p < 102 ; p++) dp[p] = -1000;// 每次dp都需要初始化
            dp[0] = 0;
            for(int i = 1; i <= n; i++)// dp求和
            {
                dp[i] = max(sum[i][j] - sum[i][k],dp[i-1] + sum[i][j] - sum[i][k]);
                ans = max(ans,dp[i]); // 更新答案
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

题目2：

就是给你一个序列 让你求这个序列的最长下降子序列 并且就子序列的方案数 这个方案数对于相同的价格序列需要去重（也就是不能多算）

这个题目的前半部分求最长下降子序列我们应该都是会求的 但是后面的计数我们要怎么考虑呢

计数的话就是从后面开始个g[i] 表示以当前第i位为结尾的最长下降子序列的长度的个数 当满足

dp[i] = dp[j] + 1 并且 a[j] > a[i] 那么就说明g[i] 可以由 g[j] 转移过来 g[i] += g[j]; 现在考虑怎么去重

假设我现在有如右一个下降子序列 5 4 3 …. 2 1 那么如果在 3 的后面还有一个3的话 是不是后面的3能够构成的下降子序列我前面的这个3其实也是能够构成的 那么我们去重的话就可以从这里入手 我们设值一个g数组，g[i]表示以i为结尾的最长下降子序列有多少个 这时候从i往前面扫过去 如果前面的a[j] == a[i] 的话 就把g[j]置为0 这样就不会出现重复的情况了 简单的来说就是把a[j] 的方案数嫁接到了 a[i] 上面了 因为序列等效了 就没有必要有g[j]了

代码如下：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e3 + 10;

int a[maxn],dp[maxn],g[maxn]; // 可以注意一下是倒序的 值相等的f前面有的我后面肯定也有

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 0 ; i < n; i++)
    {
        scanf("%d",&a[i]);
    }
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        dp[i] = 1;
        for(int j = 0; j < i; j++)
        {
            if(a[i] < a[j]) dp[i] = max(dp[i],dp[j] + 1);
        }
        if(dp[i] == 1) g[i] = 1;
        for(int j = 0; j < i; j++) // 防止后面又多算了
        {
            if(a[j] == a[i]) g[j] = 0;
        }
        for(int j = 0; j < i; j++)
        {
            if(a[i] < a[j] && dp[i] == dp[j] + 1) g[i] += g[j];
        }
        ans = max(ans,dp[i]);
    }
    printf("%d ",ans);
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        //cout<<g[i]<<endl;
        if(dp[i] == ans) cnt += g[i];
    }
    printf("%d",cnt);
    return 0;
}

题目3：给你一堆箱子的长宽高 问你对多能够利用这些箱子叠的多高 注意就是底面一直要是能够完全覆盖的

##

思路 ：一个箱子可以有六种形态 假设初始给的 x y z 那么我们可以有 x为长 y宽的长方形为底 z为高 的立方体 也可以有以x为长 y为宽的长方形 z为高的长方体 所以共有6种 预先按照 底面的长方形 的长与宽先排序 （如果不排序取的不是最优的） 设dp[i] 表示第i个能够构成的最长高 边界条件 dp[1] = rec[i].h 最值目标 max(dp[i]) ;转移方程： dp[i] = max(dp[i],dp[j]+rec[i].h);

#include<iostream>
#include<algorithm>

using namespace std;
const int maxn = 200;

int dp[maxn];
int m = 0;
struct node{
    int x;
    int y;
    int h;
}rec[maxn];
void add(int a,int b,int c) // 将一个长方形的六种状态加入候选集合
{
    rec[m].x = a,rec[m].y = b,rec[m].h = c,m++;
    rec[m].x = a,rec[m].y = c,rec[m].h = b,m++;
    rec[m].x = b,rec[m].y = a,rec[m].h = c,m++;
    rec[m].x = b,rec[m].y = c,rec[m].h = a,m++;
    rec[m].x = c,rec[m].y = b,rec[m].h = a,m++;
    rec[m].x = c,rec[m].y = a,rec[m].h = b,m++;
}
bool cmp(node a,node b) // 按照宽优先排序 然后再长
{
    if(a.x!=b.x)
        return a.x>b.x;
    return a.y>b.y;
}

int main()
{
    int n,t = 1;
    while(cin>>n)
    {
        m = 0;
        if(!n)
            break;
        int a,b,c,ans = 0;
        for(int i = 0; i < n; i++)
        {
            cin>>a>>b>>c;
            add(a,b,c);
        }
        sort(rec,rec+m,cmp);
        for(int i = 0; i < m; i++)
        {
            dp[i] = rec[i].h;
            for(int j = 0; j <= i; j++)
            {
                if(rec[j].x>rec[i].x&&rec[j].y>rec[i].y)
                dp[i] = max(dp[i],dp[j]+rec[i].h);
                ans = max(ans,dp[i]);
            }
        }
        cout<<"Case "<<t<<": maximum height = "<<ans<<endl;
        t++;
    }
}

题目 4： 求最长上升公共子序列 并且要求记录所有的路径

前一问的话我们之前其实是都学过的 这题的难点就是在于后面的求出所有的公共路径的，求公共路径我们需要用到两个辅助数组，这两个数组的作用是一样的，只是作用的串不一样 ， posa [i] [j] 表示第i位之前字符j第一次出现的位置 具体看代码

代码如下：

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;

const int maxn = 100;

int dp[maxn][maxn],posa[maxn][30],posb[maxn][30],tot = 0,t_len;
char a[maxn],b[maxn];
string ans[1000];

void dfs(string s,int x,int y,int len)
{
    if(s.size() == t_len)
    {
        reverse(s.begin(),s.end()); // 因为是从前面往后面找的 所以在这里需要翻转一下
        ans[tot++] = s;return ;
    }
    if(x < 1 || y < 1) return ;
    if(a[x] == b[y]) 
    {
        dfs(s + a[x], x - 1,y - 1,len - 1);
    }
    else // 两个不相等的话 那么只能从前面相等的部分去找了
    {
        for(int i = 0; i < 26; i++)
        {
            if(dp[posa[x][i]][posb[y][i]] == len) //找到前面最近的相同的节点 并且长度等于我接下来的长度
            {
                dfs(s,posa[x][i],posb[y][i],len);
            }
        }
    }
}


int main()
{
    string x,y;
    cin>>x>>y;
    for(int i = 0; i < x.size(); i++) a[i + 1] = x[i];
    for(int j = 0; j < y.size(); j++) b[j + 1] = y[j];
    int n = x.size(),m = y.size();
    for(int i = 1; i <= n; i++) // 求最长公共上升子序列
    {
        for(int j = 1; j <= m; j++)
        {
            if(a[i] == b[j])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
        }
    }
    t_len = dp[n][m];
    for(int i = 1; i <= n; i++) // 记录i前面离i最近的字符j的位置在哪里
    {
        for(int j  = 0; j < 26; j++)
        {
            if(a[i] == 'a' + j) posa[i][j] = i; 
            else posa[i][j] = posa[i - 1][j]; // 可能为0 也就是没有这个字符
        }
    }
    for(int i = 1; i <= m; i++)
    {
        for(int j = 0; j < 26; j++)
        {
            if(b[i] == 'a' + j) posb[i][j] = i;
            else posb[i][j] = posb[i-1][j];
        }
    }
    string s = "";
    dfs(s,n,m,t_len);
    sort(ans,ans + tot); // 按照升序输出
    for(int i = 0; i < tot; i++)
    {
        cout<<ans[i]<<endl;
    }
    return 0;
}

区间dp

区间DP过程大致相同，大都满足第一层循环枚举长度，第二层循环枚举起点。最内层往往有两种形式，第一种是需要在[i,j]中找一个分割点k使得将[i,j]分成[i,k]和[k+1,j]这样两个区间能够得到最优解

第二种形式是[i,j]可以由[i,j-1]或者[i,j+1]转移过来.重要的是找出新添加的元素（可以是k或者i）与之前那个len-1长度区间的关系

题目5：多边形游戏”是一款单人益智游戏。

游戏开始时，给定玩家一个具有N个顶点N条边（编号1-N）的多边形，如图1所示，其中N = 4。

每个顶点上写有一个整数，每个边上标有一个运算符+（加号）或运算符*（乘号）。

1179_1.jpg

第一步，玩家选择一条边，将它删除。

接下来在进行N-1步，在每一步中，玩家选择一条边，把这条边以及该边连接的两个顶点用一个新的顶点代替，新顶点上的整数值等于删去的两个顶点上的数按照删去的边上标有的符号进行计算得到的结果。

下面是用图1给出的四边形进行游戏的全过程。

1179_2.jpg

最终，游戏仅剩一个顶点，顶点上的数值就是玩家的得分，上图玩家得分为0。

请计算对于给定的N边形，玩家最高能获得多少分，以及第一步有哪些策略可以使玩家获得最高得分

思路：区间dp问题，思路的话就是上面讲的区间dp的第一种形式 我们可以设dp[l] [r] 表示区间能够获得的最大值 那么这个区间肯定是由两个子区间通过两个子区间之间的乘号或者加号连接起来的 需要在[i,j]中找一个分割点k使得将[i,j]分成[i,k]和[k+1,j]这样两个区间能够得到最优解dp[l] [j] 不过这个题目因为有乘号和负数的干扰 所以我们还是需要记录区间的最小值和最大值这两个属性 因为区间的最大值可能有两个最大的整数转移过来 也有可能由两个最小的整数相乘转移过来 环形的处理的话就是将其拆乘一个链。

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 510;

const int MA = 1e9+10;

char a[maxn];
int num[maxn];
int dpmax[maxn][maxn],dpmin[maxn][maxn];

vector<int> ans;
int main()
{
    int n;
    cin>>n;
    memset(dpmax,-128,sizeof(dpmax));
    memset(dpmin,0x3f3f,sizeof(dpmin));
    for(int i = 0; i < 2*n; i++)
    {
        if(i%2==0)
        {
            cin>>a[i];
            a[i+2*n] = a[i];
        }
        else
        {
            cin>>num[i];
            num[i+2*n] = num[i];
            dpmin[i][i] = num[i];
            dpmax[i][i] = num[i];
            dpmin[i+2*n][i+2*n] = num[i];
            dpmax[i+2*n][i+2*n] = num[i];
        }
    }
    for(int len = 2; len <= 2*n; len+=2) // 枚举区间长度  1 3 5
    {
        for(int l = 1; l + len  <= 4*n ; l+=2) 
        {
            int r = len + l ;// 枚举左右区间
            for(int k = l; k < r; k+=2)
            {
                if(a[k+1]=='t')
                {
                    dpmax[l][r] = max(dpmax[l][r],dpmax[l][k]+dpmax[k+2][r]); // 加的话最大值肯定是取最大
                    dpmin[l][r] = min(dpmin[l][r],dpmin[l][k]+dpmin[k+2][r]); // 最小值肯定是取最小
                }
                else
                {
                    dpmax[l][r] = max(dpmax[l][r],dpmax[l][k]*dpmax[k+2][r]); // *的话有两个方向 一个是最大值 和最大值过来
                    dpmax[l][r] = max(dpmax[l][r],dpmin[l][k]*dpmin[k+2][r]); // 还有就是最小值和最小值过来 因为存在负数
                    dpmin[l][r] = min(dpmin[l][r],dpmin[l][k]*dpmin[k+2][r]); // 最小的的转移就是最小的最小 还有可能是大的乘以一个负数
                    dpmin[l][r] = min(dpmin[l][r],dpmax[l][k]*dpmin[k+2][r]); // 左右两边都转移一下
                    dpmin[l][r] = min(dpmin[l][r],dpmin[l][k]*dpmax[k+2][r]);
                }
            }
        }
    }
    int ret = 0;
    for(int i = 1; i <= 2*n; i+=2) ret = max(ret,dpmax[i][2*n+i-2]);
    for(int i = 1; i <= 2*n; i+=2) if(dpmax[i][2*n+i-2]==ret) ans.push_back((i+1)/2);
    cout<<ret<<endl;
    for(int i = 0; i < ans.size(); i++) cout<<ans[i]<<" ";
    return 0;


}

题目6 ： 求一个区间有多少个回文子序列 注意子序列是可以不连续的

思路：

因为是区间dp 那么我们就可以想到用dp[i] [j]来表示区间l到r之间的回文串的个数 边界条件就是l == r 此时dp[l] [r] = 1 对于任意一个区间都有状态转移方程 dp[l] [r] =(dp[l] [r-1] + dp[l+1] [r] - dp[l+1] [r-1] + mod) % mod; 这个式子画一个图 在利用容斥原理就可以的出来 然后就是要特判一下如果s[l] == s[r] 的画 就需要再加上

dp[l] [r] = (dp[l+1] [r-1] + dp[l] [r] + 1 + mod) % mod; 以为上面的式子成立的花 那么就可以多 dp[l+1] [r-1] 个回文串 加1的话是加上 s[l] 与 s[r] 这两个字符组成的回文串

#include <bits/stdc++.h>

using namespace std;

const int maxn = 110;
const int mod = 10007;
int dp[maxn][maxn];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        string s;
        cin>>s;
        for(int i = 0; i < maxn; i++)
        {
            for(int j = 0;j < maxn; j++)
            {
                if(i == j) dp[i][j] = 1;
                else dp[i][j] = 0;
            }
        }
        //cout<<s.size()<<endl;
        for(int len = 1; len < s.size(); len ++)
        {
            for(int l = 0; l + len < s.size(); l++)
            {
                int r = len + l;
                dp[l][r] =(dp[l][r-1] + dp[l+1][r] - dp[l+1][r-1] + mod) % mod; // 这个区间回文串的个数等于 容斥原理
                if(s[l] == s[r]) dp[l][r] = (dp[l+1][r-1] + dp[l][r] + 1 + mod) % mod;
            }
        }
        printf("%d\n",dp[0][s.size()-1]);
    }
    return 0;
}

题目7 有n个人排成一排要上台表演，每个人有一个屌丝值pi。第i个上台表演的人，他的不满意度为(i-1)*pi。

现在有一个类似于栈的黑屋子，你可以让某些人进入这个黑屋子。这些人要按照排的顺序来，那么对于排在最前面的人，

就有两个选择：

（1）让他直接上台表演；

（2）让他暂时进黑屋子。

现在请你选择一个合理的调度顺序，使得最后的总不满意度最小？

思路：这个可以划分成一个个子区间来求解 设dp[l] [r] 表示l 到 r直接最小的屌丝值为多少，那么我们肯定关心的就是第一个人到底是排在第几位的 如果他排在第k位的话 那么 2 ~（ l + k - 1） 这些人肯定就排在他的前面 就可以再把 2 ~（ l + k - 1）这里人在看成一个子区间来求解 (l + k) ~ r 这些人肯定排在前面的k个人后面 我们就得把前面的k个人对于他们的影响给消除掉 也就是在这个基础上加上 k * (sum[r] - sum[l + k - 1]) 那么对于后面的 (l + k) ~ r这个区间就又可以看成一个子区间来求解

代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn  = 110;

const int inf = 0x3f3f3f3f;

int dp[maxn][maxn],sum[maxn],a[maxn];

int solve(int l,int r)
{
    int ans = dp[l][r];
    if(ans != inf) return dp[l][r];
    if(l >= r) return 0;
    for(int i = l; i <= r; i++)
    {
        for(int k = 1; k <= r - l + 1;k ++) // 这个其实可以看作一个个区间的子问题 那么就可以用区间dp来写
        {
            ans = min(ans,solve(l + 1,l + k - 1) + (k - 1)*a[l] + k * (sum[r] - sum[l + k - 1]) + solve(l + k,r)); // 第k个上场的话 产生
        }
    }
    return dp[l][r] = ans;
}

int main()
{
    int t,cas = 0;
    cin>>t;
    while(t--)
    {
        cas++;
        int n;
        scanf("%d",&n);
        memset(dp,0x3f,sizeof dp);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&a[i]);
            sum[i] = sum[i - 1] + a[i];
        }
    
        printf("Case #%d: %d\n", cas, solve(1,n));
    }
    return 0;
}

树形dp

树的特征

1.N个点 只有N-1条边的无向图

2.无向图里 任意两点有且只有一条路

3.一个点只有一个前驱 但可以有多个后继

4.无向图没有环

树形DP

由于树有着天然的递归结构 父子结构 而且它作为一种特殊的图 可以描述许多复杂的信息 因此在树就成了一种很适合DP的框架

问题：给你一棵树 要求用最少的代价（最大的收益）完成给定的操作

树形DP 一般来说都是从叶子从而推出根 当然 从根推叶子的情况也有 不过很少（本蒟蒻还没有做到过~）

一般实现方式: DFS(包括记忆化搜索)，递推等

题目8：

就是给你一棵树，每个节点有一个权重，如果你选择了根节点的话 那么他的子节点就不能再次选择，如果你选择子节点的话那么根节点就不能在选

如果是线型的一串一维数组的话 不能选择相邻的数字 要让选择的数的和最大

那么就有递推方程dp[i] = max(dp[i-1],dp[i-2] + a[i])

max里面前一个式子代表我不选a[i] 那么就能从dp[i-1] 转移过来 后面一个代表我选了这个 那么就是从dp[i-2] + a[i] 转移过来

两者取最大值就是我们需要的答案 那么这题的话就可以用这个思想

如果我们选择了这个节点的值的话 我们就只能从这个节点出发的下下一层转移了 下一层不能选了

如果我们不选这个节点 我们直接从下一层节点转移就好了 两者取最大值

代码如下 ：

#include<bits/stdc++.h> // 第一个写的代码比较垃圾 

using namespace std;

const int maxn = 6010;

int val[maxn] , in[maxn];

int dp[maxn] = {0};// 记忆化优化 相当于剪枝了

vector<int> g[maxn]; // 记录树

int dfs(int root)
{
    int tans = dp[root]; // 如果前面搜索到了就直接输出就好了
    if(tans!=0) return tans;
    if(g[root].size() == 0) return val[root]; // 递归到叶子节点直接返回
    int ans = val[root] , ans1 = 0 ;// ans 代表我选择了这个节点 ans1 代表我不选择这个节点
    for(int i = 0 ; i < g[root].size(); i++) // 第一层
    {
            for(int j = 0 ; j < g[g[root][i]].size(); j++) 
            {
                ans += dfs(g[g[root][i]][j]);// 那么按照刚才的思路 ans就是从下下一层转移
            }
            ans1 += dfs(g[root][i]);// 我不选这个就可以直接从这一层转移
            tans = max(ans1,ans); // 两者取一下最大值
    }
    return dp[root] = tans; // 记忆化 避免很多的多余运算
}

int main()
{
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        cin>>val[i];
    }
    int u,v;
    while(cin>>u>>v&&u!=0)
    {
        g[v].push_back(u);
        in[u]++;
    }
    int root , ans = 0;
    for(int i = 1; i <= n; i++)
    {
        if(in[i]==0) root = i; // 找到根节点开始dfs
    }
    ans = dfs(root);
    cout<<ans<<endl;

}

对于树形dp中的换根(二次扫描法) 题目一般会让你算出以每一个节点为根的某些值 然后再在这些值中取最大值或者最小值，这时候你就需要找到每个根节点直接的练习，利用第一次dfs出来的数据，再根据节点之间的关系，进行第二次dfs算出以其他节点为根的时候的最大值

题目9：首先给你一颗树 树的叶子节点就是汇点，就是可以无穷尽的流出水量，每条边有一个权值说明这条边的最大能够流出的水量，现在让你选择一个根节点，也就是源点，源点可以流出无穷多的水量，问你选择那一个节点为源点能够让流出的总水量最大。

思路：dfs+换根 因为这个题目是让你选择一个节点，然后这个根节点的出水量最大，如果你每一个节点每一个节点的去dfs一次的话，时间复杂度肯定是爆炸的，其实我们可以找规律，然后利用一次dfs进行第二次dfs算出来的值推出用其他节点做为源点（也就是根节点）是的最大流水，也就是二次扫描。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int maxn = 4e5+10;
const int inf = 1000000000;

typedef long long ll;
ll t_ans = 0;
ll sz[maxn];

vector< pair<int,ll> > g[maxn]; // 第一个为u节点 第二个为权值

ll dfs1(int son,int fa)
{
    if(g[son].size() == 1) return inf;
    ll sum = 0;
    for(int i = 0; i < g[son].size(); i++)
    {
        int u = g[son][i].first;
        ll w = g[son][i].second;
        if(u==fa) continue;
        ll temp = dfs1(u,son);
        sum += min(w,temp);
    }
    sz[son] = sum;
    return sum;
}
void dfs2(int son,int fa,ll val)
{
    if(g[son].size() == 1) return ;
    t_ans = max(t_ans,val);
    for(int i = 0; i < g[son].size(); i++)
    {
        int u = g[son][i].first;
        if(u==fa || g[u].size() == 1) continue;
        ll w = g[son][i].second;
        ll temp = sz[u] + min(w,val - min(w,sz[u]));
        dfs2(u,son,temp);
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        t_ans = 0;
        scanf("%d",&n);
        for(int i = 1; i <= n; i++)
        {
            g[i].clear();
        }
        for(int i = 0; i < n - 1; i++)
        {
            int u,v;
            ll w;
            scanf("%d%d%lld",&u,&v,&w);
            g[u].push_back(make_pair(v,w));
            g[v].push_back(make_pair(u,w));
        }
        ll ans = dfs1(1,-1);
        dfs2(1,-1,ans);
        printf("%lld\n",t_ans);
    }
    return 0;
}

题目10： 就是问你以每个节点为根的树离叶子节点最长的距离是多少，一次输出每一个节点的距离

思路 ：dfs + 换根 也就是二次dfs扫描 不过这个题目需要记录一个最大值和次大值才能完成二次dfs

代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;
int n;
int e[maxn],ne[maxn],idx,h[maxn],val[maxn];
int szma[maxn],szmi[maxn],in[maxn],t_ans[maxn];
void add(int a,int b,int w)
{
    e[idx] = b,ne[idx] = h[a],val[idx] = w,h[a] = idx++;
}

int dfs1(int now,int fa)
{
    szma[now] = 0,szmi[now] = 0;
    for(int i = h[now]; i != -1; i = ne[i])
    {
        int j = e[i],w = val[i];
        if(j == fa) continue;
        int ne_ma = dfs1(j,now);
        if(szma[now] <= w + ne_ma)
        {
            int temp = szma[now];
            szma[now] = w + ne_ma; // 更新最大值
            szmi[now] = temp; // 更新次大值
        }
        if(w + ne_ma < szma[now] && w + ne_ma >= szmi[now]) szmi[now] = ne_ma + w;
    }
    return szma[now];
}

void dfs2(int now,int fa,int mid,int mid2) // 传入一个最大的和次二大的
{
    for(int i = h[now]; i != -1; i = ne[i])
    {
        int j = e[i],w = val[i];
        if(j == fa) continue;
        int tempmid = mid,tempmid2 = mid2;
        if(tempmid != szma[j] + w)
        {
            if(szma[j] < tempmid + w)
            {
                tempmid2 = szma[j];
                tempmid = tempmid + w;
            }
            else
            {
                tempmid2 = max(tempmid + w,szmi[j]);
                tempmid = szma[j];
            }
            t_ans[j] = tempmid;
            dfs2(j,now,t_ans[j],tempmid2);
        }
        else
        {
            if(szma[j] > tempmid2 + w) // 是由我这个更新过来的
            {
                tempmid2 = max(szmi[j],tempmid2 + w);
                tempmid = szma[j];
                t_ans[j] = tempmid;
                dfs2(j,now,t_ans[j],tempmid2);
            }
            else // szma[j] <= tempmid2 + w;
            {
                tempmid = tempmid2 + w;
                tempmid2 = szma[j];
                t_ans[j] = tempmid;
                dfs2(j,now,t_ans[j],tempmid2);
            }
        }
    }
}
void init()
{
    idx = 0;
    for(int i = 0; i <= n; i++) ne[i] = 0;
    for(int i = 0; i <= n; i++) h[i] = -1;
    for(int i = 0; i <= n; i++) e[i] = 0;
    for(int i = 0; i <= n; i++) t_ans[i] = 0;
    for(int i = 0; i <= n; i++) val[i] = 0;
    for(int i = 0; i <= n; i++) szma[i] = 0;
    for(int i = 0; i <= n; i++) szmi[i] = 0;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
    init();
    for(int i = 2 ; i <= n; i++)
    {
        int u,w;
        scanf("%d%d",&u,&w);
        add(i,u,w);
        add(u,i,w);
    }
    int ans = dfs1(1,-1);
    t_ans[1] = ans;
    dfs2(1,-1,ans,szmi[1]);
    for(int i = 1; i <= n; i++)
    {
        printf("%d\n",t_ans[i]);
    }
    }
    return 0;
}

题目11： 给你一颗树 让你任选一个节点为根节点 你要最大化所有子树的顶点数之和 让你输出这个最大值

思路： dfs加换根 到时候具体画图来解释

代码如下：

#include<iostream>
#include<vector>
#include<cstdio>

using namespace std;


typedef long long ll;

const int maxn = 2e5+10;

ll sz[maxn],ans = 0,n;

vector<int> g[maxn];

void dfs1(int son,int fa)
{
    for(int i = 0; i < g[son].size(); i++)
    {
        int u = g[son][i];
        if(u==fa) continue;
        dfs1(u,son);
        sz[son] += sz[u];
    }
    sz[son] += 1;
    ans += sz[son];
}
void dfs2(int son,int fa,ll val)
{
    for(int i = 0; i < g[son].size(); i++)
    {
        int u = g[son][i];
        if(u==fa) continue;
        ll mid = val - sz[u] + n - sz[u]; // 左子树的大小是等于 n - sz[u]的
        ans = max(ans,mid);
        dfs2(u,son,mid);
    }

}
int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n - 1; i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1,-1);
    dfs2(1,-1,ans);
    //cout<<sz[1]<<endl;
    cout<<ans<<endl;
}