P1352 没有上司的舞会

树形Dp基础题

设两个数组g,f.g[i]表示选节点i的最优值,f[i]表示不选节点i的最优值。

显然g[i]=∑f[to],f[i]=max(g[to],f[to])。

这题没给根，跳fa找到根，

然后dfs一遍就行了。

#include<iostream>
#include<cstdio>
using namespace std;
const int N=6005;
int n,cnt;
int ri[N],f[N],g[N],fa[N],head[N];
struct node{
    int to,nxt;
}e[N<<1];
void add(int to,int from){
    e[++cnt]=(node){to,head[from]};
    head[from]=cnt;
}
void dfs(int x){
    g[x]=ri[x];
    for(int i=head[x];i;i=e[i].nxt){
        if(e[i].to!=fa[x]){
            dfs(e[i].to);
            g[x]+=f[e[i].to];
            f[x]+=max(g[e[i].to],f[e[i].to]);
        }
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&ri[i]);
    int x,y;
    for(int i=1;i<=n;++i)
        fa[i]=i;
    for(int i=1;i<n;++i){
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
        fa[x]=y;
    }
    scanf("%d%d",&x,&y);
    int s=n;
    while(s!=fa[s])
        s=fa[s];
    dfs(s);
    printf("%d",max(max(f[s],g[s]),0));
    return 0;
}