Espace virtuel de code
L'espace interne de la fonction est stocké dans la pile C++La taille par défaut de l'espace de pile est4M Il est donc facile d'ouvrir la pile à l'intérieur de la fonction
Variables globales les variables statiques sont stockées dans le tas

ArbreDP AcWing 285. Un bal sans patron.

Lien vers la question originale

AcWing 285. Un bal sans patron.

Étiquette de l'algorithme

Planification dynamique ArbreDP

Idées

Calcul de l'état

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;
    // Requête du noeud racine
    while(p[root]){
        root++;
    }
    dfs(root);
    printf("%lld", max(f[root][0], f[root][1]));
    return 0;
}

L'originalité n'est pas facile
Réimpression Veuillez indiquer la source
Si ça t'aide N'oublie pas de me soutenir.