#|Codeforces Round #530 (Div. 2) F. Cookies（树形DP+线段树）树形DP|线段树|贪心

题目链接题意给你一棵树有n鸽节点，节点编号1-n，每个节点上有xi鸽饼干，每个节点上吃饼干吃一块需要pi时间
再给你每个节点的父亲，和经过这条边所花费时间
【#|Codeforces Round #530 (Div. 2) F. Cookies（树形DP+线段树）】刚开始你在起点，两个人轮流进行以下步骤，你先手
你：移动到子节点，或者结束游戏并移动到根节点，选择性吃沿途饼干
对手：删一条你所在节点到儿子的边，或者什么都不做
你现在有T的时间求最多能吃多少饼干。
思路从根节点开始深搜，对当前点求

当前节点直接返回，可吃最多饼干
所有儿子节点的可吃最多饼干。
所有儿子节点的可吃次多饼干。

对手会删除最大权边，返回max(1,2)即可，由于你先手，根节点返回max(1,3)
然后对于当前节点可吃饼干数，用线段树维护所有花费时间的饼干数量。
代码

#include using namespace std; #define ll long long #define N 100005 #define lson rt<<1, l, mid #define rson rt<<1|1, mid+1, rll val[1000005<<2], cnt[1000005<<2]; void ins(ll rt, ll l, ll r, ll num, ll t) { val[rt] += t*num, cnt[rt] += num; if(l == r) return; ll mid = (l+r)>>1; if(t <= mid) ins(lson,num,t); else ins(rson,num,t); }ll get(ll rt, ll l, ll r, ll t) { if(val[rt] <= t) return cnt[rt]; if(l == r) return t/r; // 上面一行已经保证t/r>1; if(val[rt<<1] >= t) return get(lson,t); return get(rson,t-val[rt<<1])+cnt[rt<<1]; }ll xi[N], ti[N]; struct Node { int v, w; }st; vector e[N]; ll dfs(ll u, ll t) { ins(1,1,1000000,xi[u],ti[u]); ll f1 = get(1,1,1000000,t); ll f2 = 0, f3 = 0; for(auto now : e[u]) { if(t <= now.w*2) continue; ll v = now.v; ll tmp = dfs(v,t-2*now.w); if(tmp > f2) f3 = f2, f2 = tmp; else if(tmp > f3) f3 = tmp; } ins(1,1,1000000,-xi[u],ti[u]); if(u == 1) return max(f1,f2); return max(f1,f3); }int main() { ll n, t, u; scanf("%lld%lld",&n,&t); for(ll i = 1; i <= n; ++i) scanf("%lld",&xi[i]); for(ll i = 1; i <= n; ++i) scanf("%lld",&ti[i]); for(ll i = 2; i <= n; ++i) { scanf("%lld%lld",&u,&st.w); st.v = i; e[u].push_back(st); } printf("%lld\n",dfs(1,t)); return 0; }