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

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

  1. 当前节点直接返回,可吃最多饼干
  2. 所有儿子节点的可吃最多饼干。
  3. 所有儿子节点的可吃次多饼干。
对手会删除最大权边,返回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; }

    推荐阅读