题解 P1122 【最大子树和】

vegetabird · 2017-08-06 14:02:08 · 题解

怎么楼下所有题解全是DFS? 其实随便找一个根，把所有点按到根的距离排个序就可以不用DFS了。至于思路没有什么不同，用f1表示包含根的最大子树和，f2表示不包含根的最大子树和。至于排序，把所有点BFS一遍，产生的队列就是排序后的点，完全不需要sort

#include<cstdio>
#include<cctype>
using namespace std;
inline void getint(int &_int){
    char ch=_int=0;
    bool neg=false;
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-'){
        neg=true;
        ch=getchar();
    }
    while(isdigit(ch)){
        _int=_int*10+ch-48;
        ch=getchar();
    }
    if(neg)_int=-_int;
}
int n;
int a[32010],b[32010],fst[16010],nxt[32010];
int father[16010];
int f1[16010],f2[16010];
int q[16010];
bool vis[16010];
const int INF=0x3fffffff;
inline int max(const int &a,const int &b){
    return a>b?a:b;
}
int main(){
    register int i,k,u,head,tail;int maxrt=-INF;
    getint(n);
    for(i=1;i<=n;i++){
        getint(f1[i]);
        maxrt=max(maxrt,f1[i]);
    }
    for(i=1;i<2*n-1;i+=2){
        getint(a[i]);getint(b[i]);
        a[i+1]=b[i],b[i+1]=a[i];
        nxt[i]=fst[a[i]];
        fst[a[i]]=i;
        nxt[i+1]=fst[b[i]];
        fst[b[i]]=i+1;
    }
    if(maxrt<0){
        printf("%d\n",maxrt);
        return 0;
    }
    head=0,tail=1,q[0]=1;
    vis[1]=true;
    while(head!=tail){
        u=q[head++];
        for(k=fst[u];k;k=nxt[k]){
            if(!vis[b[k]]){
                father[b[k]]=u;
                q[tail++]=b[k];
                vis[b[k]]=true;
            }
        }
    }
    while(tail>0){
        u=q[--tail];
        f1[father[u]]+=max(f1[u],0);
        f2[father[u]]=max(f2[father[u]],max(f1[u],f2[u]));
    }
    printf("%d\n",f2[0]);
}