Tree DP acwing 285. dance without boss

Code virtual space
The internal space of the function is stored in the stack C++ The default stack space size is 4M Therefore, it is easy to burst the stack inside the function
Global variables static variables are stored in the heap

Tree form DP AcWing 285. A dance without a boss

Original link

AcWing 285. A dance without a boss

Algorithm tags

Dynamic programming Tree form DP

Ideas

State calculation

Code

#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
const int N = 6005;
int a[N], e[N], h[N], ne[N], idx;
int f[N][2];
bool p[N];
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
void add(int a, int b){
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
void dfs(int u){
    f[u][1]=a[u];
    for(int i=h[u]; i!=-1; i=ne[i]){
        int j=e[i];
        dfs(j);
        f[u][1]+=f[j][0];
        f[u][0]+=max(f[j][0], f[j][1]);
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n=read();
    rep(i, 1, n+1){
        a[i]=read();
    }
    memset(h, -1, sizeof h);
    rep(i, 0, n-1){
        int a=read(), b=read();
        add(b, a);
        p[a]=true;
    }
    int root=1;
    //  Query root node 
    while(p[root]){
        root++;
    }
    dfs(root);
    printf("%lld", max(f[root][0], f[root][1]));
    return 0;
}

Originality is not easy.
Reprint please indicate the source
If it helps you Don't forget to praise and support