题解 P1122 【最大子树和】

· · 题解

似乎不用找根，然而蒟蒻还是找了根。。。。

然后N^2就TLE.....

然后我发现似乎有重复计算，记忆化大法好.............开了个map，记录u点以fa为父节点时的dp值，然后好像还挺快

#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<cstring>
#include<utility>
#define maxn 16003
using namespace std;
inline void read(int &num){
    char c;num=0;bool flag=0;
    while((c=getchar())==' '||c=='\r'||c=='\n');
    if(c=='-')flag=1;
    else num=c-48;
    while((c=getchar())>=48&&c<=57)num=num*10+c-48;
    if(flag)num*=-1;
    return;
}
vector<int>sons[maxn];
map<pair<int,int>,int> m;
int n,a[maxn],dp[maxn],g[maxn];
void DFS(int u,int fa){
    pair<int,int> tmp=make_pair(u,fa);
    map<pair<int,int>,int>::iterator it=m.find(tmp);
    if(it!=m.end()){
        dp[u]=m[tmp];
        if(dp[u]>0) g[fa]+=dp[u];
        return;
    }
    int size=sons[u].size();
    for(int i=0;i<size;++i)
        if(sons[u][i]!=fa) 
            DFS(sons[u][i],u);
    dp[u]=max(0,max(a[u],a[u]+g[u]));
    m[tmp]=dp[u];
    if(dp[u]>0) g[fa]+=dp[u];//g[fa]表示以fa为根的子树子节点的最大价值和
    return;
}
int main(){
    freopen("a.in","r",stdin);
    read(n);
    for(int i=1;i<=n;++i) read(a[i]);
    int x,y;
    for(int i=1;i<n;++i){
        read(x),read(y);
        sons[x].push_back(y);
        sons[y].push_back(x);
    }
    int ans=-0x7fffffff;
    for(int i=1;i<=n;++i){
        memset(dp,0,sizeof(dp));
        memset(g,0,sizeof(g));
        DFS(i,0);
        ans=max(ans,dp[i]);
    }
    printf("%d",ans);
    return 0;
}