题解 P1122 【最大子树和】

· · 题解

这里讲一种我自以为是不同的方法

树形DP、BFS

不同之处就是，我们找这坨树的所有叶子结点，用多源DP反向推上去。

DP思路：

所以说这里很好想的。用f[ i ]表示f[ i ]为根的子树的美观度最大值。那么

f[ i ]=max(0,now[ i ]+{f[ son ]})这里i表示当前结点，

{f[ son ]}：所有的儿子的美观度和，

now[ i ]：当前结点的美观度。之所以与0取最大值，是因为如果以i为根的这坨子树的美观度最大都为负数的 话，那我不如不要。

程序设计：

我们先找叶节点,对f初始化，对于一个叶节点i,如果now[i]<0则f[i]=0,否则f[i]=now[i];

随后将叶节点全部压入队列，对于结点i，如果 f[i] (已经从其叶节点获得了值)+now[i] <0,那么后面的事情不用干了，剪掉这个子树(因为这坨子树美观度是负数)，去处理队列中下一个结点，否则找它的父结点（与它相连没访问过的），对于i的父节点j,f[j]+=max(0,f[i]),且将父节点入队（注意不要重复入队）。

另外需要注意对于一个结点i，它的子节点都还没处理完就对i进行处理

处理树的话：

把树建成有向图（边双向，其实就是无向图）叶子节点的出入度必定都是1。这样便找到了叶结点（我觉得这法子挺蠢的）

十分抱歉我不太会用那个好像叫LATEX的东西，凑合着看吧，讲的应该不错（自认为）

code:

#define maxn (16005)*2
using namespace std;
int n,h[maxn],cnt; 
int flw[maxn];  //文中now数组
struct node     //前向星
{
    int to,next;
}edge[maxn];
struct node2   //出入度
{
    int id,rd,cd;
}rcd[maxn];
void mktr()    //统计出入度
{
    for(int i = 1;i <= n;i++)
    {
        rcd[i].id=i;
        for(int j = h[i];j;j=edge[j].next)
        {
            rcd[edge[j].to].rd++;
            rcd[i].cd++;
        }
    }
}
queue<int>q;
int ind[maxn];
int inz[maxn];       //文中f数组
void bfs()
{
    for(int i = 1;i <= n;i++)
    {
        if(rcd[i].cd==1&&rcd[i].rd==1)
        {
            q.push(i);
        }
    }
    int now; //当前节点
    while(!q.empty())
    {
        now=q.front(),q.pop();
        if(ind[now]!=rcd[now].cd-1)//确定当前的儿子结点已经处理完毕
        {
            q.push(now);continue;
         } 
        ind[now]=1;
        inz[now]=max(inz[now]+flw[now],0);
        if(inz[now]<0)
            continue;
        for(int i = h[now];i;i=edge[i].next)
        {   
            if(ind[edge[i].to]<rcd[edge[i].to].cd-1)  //确认目标点访问次数没超（双保险）
            {
                if(!ind[edge[i].to])  //没入过队
                    q.push(edge[i].to);
                ind[edge[i].to]++;
                inz[edge[i].to]+=max(0,inz[now]); //父结点加上当前结点为根的子树的值
            }
            else
            {
                inz[edge[i].to]+=max(0,inz[now]); //同上
            }
        }
    }
    cout<<inz[now];
}
void add(int x,int y)
{
    cnt++;
    edge[cnt].to=y;
    edge[cnt].next=h[x];
    h[x]=cnt;
}
int main() 
{
//  freopen("testdata.in","r",stdin);
//  freopen("testdata.out","w",stdout);
    cin>>n;
    int x,y;
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&flw[i]);
    }
    for(int i = 1;i <= n-1;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    mktr();
    bfs();
//  cout<<inz[]
    return 0;
}