题解 P1122 【最大子树和】

· · 题解

树状dp的入门题，做完这道题对树有了新的理解。树不一定是我们通常理解的树（根是不变的）。树形结构代表的特点是连接和层次。

个人认为：这个题没有真正的树根只要随便找一个节点开始计算即可。

中心思想就是把连接两个点的边存起来，然后处理这个串上的边，比如这条串上的上一条边是什么，这条串的最后一个节点是什么。详细题解写到注释里了

有的地方可能解释的不清楚，大家意会吧......

代码如下：

‘’‘cpp

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int flower[16600],n,next[40010],pre[40010],last[40010],f[16600],num=0;

/* flower[i]表示第i个节点的值

next[i]表示编号为i的边的下一个节点的值

pre[i]表示编号为i的边的上一个节点相连的边的编号

last[i]表示与第i个节点相连的最后一条边的编号（因为与i节点相连的边可能不止一条）

last[i]也可以理解成许多节点用边相连形成一条串，第i条边在这个串中的上一条边就是last[i]

f[i]表示第i节点的子树的最大和

*/

bool vis[16600];//标记每个节点是否访问过
int ans=-inf;
void cnct(int x,int y)
{
    num++;//边的编号++
    next[num]=y;//第num条边的下一个节点是y
    pre[num]=last[x];//第num条边的上一条边是x的上一条边
    last[x]=num;//现在x的上一条边是num了
}
int dfs (int u)
{
    int sum=0;
    if(f[u])
    return f[u];
    int i=last[u];//u节点的上一条边
while(i)//如果有这条边
 {
        int nxt=next[i];//nxt就是此边相连的另一个节点（这条边把u与nxt相连）
        if(!vis[nxt])
        {
            vis[nxt]=1;
            int x=dfs(nxt);//往上找串
            if(x>0) sum+=x;//找完后如果子树权值和>0，加上
        }
        i=pre[i];//再找i的前一个边
    }
    f[u]=sum+flower[u];
    if(f[u]>ans) ans=f[u];
    return f[u];
}
int main()
{
    memset(flower,0,sizeof flower);
    memset(pre,0,sizeof pre);
    memset(last,0,sizeof last);
    memset(next,0,sizeof next);
    memset(f,0,sizeof f);
    memset(vis,false,sizeof vis);
    //freopen("de.txt","r",stdin);
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
    scanf("%d",&flower[i]);
    for (int i=1;i<n;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        cnct(x,y);//将两个节点连接起来
        cnct(y,x);//双向都要连接
    }
    vis[1]=1;
    dfs(1);
    printf("%d\n",ans);
    return 0;
}

’‘’ 下面补上一个利用vector存边的做法，比较好理解

代码如下：

‘’‘cpp

#include <bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
struct edge
{
    int u,v;
};
vector <edge> e[16010];//用vector数组来表示每个点相邻的点
int result=-inf,n,f[16010],flower[16010];//f[i]为节点i的子树的最大值
bool vis[16010];
int dfs (int x)
{
    int t;
    for (int i=0;i<e[x].size();++i)
    {
        edge &st=e[x][i];
        if (!vis[st.v])
        {
            vis[st.v]=1;
            t=dfs(st.v);
            if (t>0)
            f[x]+=t;
        }
    }
    result=max(result,f[x]);
    return f[x];
}
int main()
{
    memset(f,0,sizeof f);
    memset(flower,0,sizeof flower);
    memset(vis,false,sizeof vis);
    //freopen("de.txt","r",stdin);
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
    {
        scanf("%d",&flower[i]);
        f[i]=flower[i];
    }
    for (int i=1;i<n;++i)
    {
        int p1,p2;
        scanf("%d%d",&p1,&p2);
        e[p1].push_back((edge){p1,p2});
        e[p2].push_back((edge){p2,p1});
    }
    vis[1]=true;
    dfs(1);
    printf("%d\n",result);
    return 0;
}
’‘’