【例题】树上DP

/*
LBR
树形dp
https://www.luogu.org/problem/show?pid=1270
随便找了一道~~

*/
#include<bits/stdc++.h>
using namespace std;
struct node
{
    int c;
    int l;
    int r;
    int len;
};
node tree[101];
int s;
int n=0;
int ans[101][601];
int read(int u)
{
    int a,b;
    cin>>a>>b;
    tree[u].len=a<<1;
    if(b!=0)tree[u].c=b;
    else
    {
        tree[u].l=read(++n);
        tree[u].r=read(++n);
    }
    return u;
}
int dp(int u,int t)
{
    t-=tree[u].len;
    if(t<=5)return 0;
    //加这句话后快了5倍~~~~~~~
    if(ans[u][t]!=0)return ans[u][t];
    if(tree[u].c)
    {
        return min(tree[u].c,t/5);
    }
    int ln=tree[u].l;
    int rn=tree[u].r;
    for(int i=0;i<=t;i++)
    {
        ans[u][t]=max(ans[u][t],dp(ln,i)+dp(rn,t-i));
    }
    return ans[u][t];
}
int main()
{
    cin>>s;
    read(++n);
    cout<<dp(1,s-1);
}