题目链接
题意 给你一棵树有n鸽节点,节点编号1-n,每个节点上有xi鸽饼干,每个节点上吃饼干吃一块需要pi时间
再给你每个节点的父亲,和经过这条边所花费时间
【#|Codeforces Round #530 (Div. 2) F. Cookies(树形DP+线段树)】刚开始你在起点,两个人轮流进行以下步骤,你先手
你:移动到子节点,或者结束游戏并移动到根节点,选择性吃沿途饼干
对手:删一条你所在节点到儿子的边,或者什么都不做
你现在有T的时间求最多能吃多少饼干。
思路 从根节点开始深搜,对当前点求
- 当前节点直接返回,可吃最多饼干
- 所有儿子节点的可吃最多饼干。
- 所有儿子节点的可吃次多饼干。
然后对于当前节点可吃饼干数,用线段树维护所有花费时间的饼干数量。
代码
#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;
}
推荐阅读
- 数据结构和算法|LeetCode 的正确使用方式
- #|7.分布式事务管理
- #|算法设计与分析(Java实现)——贪心算法(集合覆盖案例)
- #|算法设计与分析(Java实现)—— 动态规划 (0-1 背包问题)
- #|阿尔法点亮LED灯(一)汇编语言
- #|Multimedia
- #|ARM裸机开发(汇编LED灯实验(I.MX6UL芯片))
- 基础课|使用深度优先搜索(DFS)、广度优先搜索(BFS)、A* 搜索算法求解 (n^2 -1) 数码难题,耗时与内存占用(时空复杂度)对比(附((n^2 - 1) 数码问题控
- #|学习笔记 | Ch05 Pandas数据清洗 —— 缺失值、重复值、异常值
- win10|搏一搏 单车变摩托,是时候捣鼓一下家中的小米电视机啦。