$\large{\text{一千个Oier程序中有一千种树形DP}}$
思路都差不多的，但是每个人都有自己的状态定义与转移
不妨定义$dp[i][j]$表示，在$i$子树内，偷$j$张画，且不考虑根到$i$父节点路径代价的最短时间
$a[i]$表示$i$与其父节点的距离
$d[i]$表示$i$到根节点的距离
不难想出转移
$\large{dp[i][j]=min\left\{dp[son1][k]+dp[son2][j-k]+dis[x]\right\}}$
统计答案
枚举每个节点选几个，如果$dp[i][j]+d[i]-a[i]<=s$，更新答案
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int size[],s,cnt,a[],v[],e[][],dp[][],ans,d[];
void init(int x)
{
int t,to;
if(scanf("%d%d",&t,&to)!=)
return;
d[x]+=*t,a[x]=*t,dp[x][]=;
if(to)
v[x]=to;
else
{
d[++cnt]=d[x],init(e[x][]=cnt);
d[++cnt]=d[x],init(e[x][]=cnt);
}
}
void dfs(int x)
{
if(!x)
return;
dfs(e[x][]),dfs(e[x][]);
size[x]=v[x]+size[e[x][]]+size[e[x][]];
if(v[x])
for(int i=;i<=v[x];i++)
dp[x][i]=a[x]+dp[x][]+*i;
else
for(int i=;i<=size[x];i++)
for(int j=;j<=i;j++)
dp[x][i]=min(dp[x][i],dp[e[x][]][j]+dp[e[x][]][i-j]+a[x]);
}
int main()
{
scanf("%d",&s);
memset(dp,0x3f,sizeof(dp));
init(++cnt);
dfs();
for(int i=;i<=cnt;i++)
for(int j=;j<=size[i];j++)
if(dp[i][j]+d[i]-a[i]<s)
ans=max(ans,j);
printf("%d\n",ans);
return ;
}