ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 E: 世末农庄

内存限制：256 MB 时间限制：3 S
题面：传统 评测方式：文本比较 上传者：
提交：1 通过：1
返回比赛提交提交记录

题目描述

    西元???? 年，星球”泰拉”发生了核战争，整个地上世界成为了一片废土，由于辐射，异变生
物已经占领了地上世界。
    矮人族先西为了生存，不得不隐入地下进行生存。
幸好！先西的老祖宗早有远见，开发了地下农庄。地下农庄是一个家中地下室为根（记根的
编号为0）的树形结构，由于老祖宗没有留下地图，先西只能进行探索，以找寻农庄中每个农
田的具体位置。
    先西带着升降滑索和背包进入了农庄，并把锚点打在了家中的地下室。也就是说，它可以在
回家时从当前所在位置到根的简单路径上获取农田中的农作物。
    先西发现，不同农田的农作物所能提供的营养参差不齐，每单位农作物能得到的粮食不同。简

单来说，某一层的粮食产出符合如下公式：



    粮食重量=该田农作物的营养值p·该田剩余农作物重量w



    并且，越是到达深层，环境越是恶劣，农田的农作物营养值总是不如上一层直接相邻农田的
营养值高。
    此外，由于极少数异变蝗虫会钻地以获取食物，某些已经发现的农田可能因此被一扫而空。
为了简化问题，每天仅会发生下列三种事情之一：
• 发现新的农田，编号记为u，其与某一个已知的编号为v的农田相通（注意地下农庄是
一个树形结构），该农田农作物的营养值为pu，农作物重量为wu，且由于深处环境更加
恶劣，总是有pu<pv；
• 回家整理行装，此时先西在编号为k的农田，打算沿着最短路径回到地下室（根），背
包还能装s个单位重量的农作物，此时需要输出先西最多能得到多少粮食重量（先西总
是优先保证这一天带走的农作物能够生产最多粮食），注意每次获取农作物后，农作物
剩余量会减少；
• 异变蝗虫入侵，此时编号为l的农田中，农作物被一扫而空。
现在对于接下来q天，根据已知的地下农庄结构，背包剩余重量空间，每次回家时先西应当
如何决策以获得最多的粮食回到地下室？
简单地说：
初始有一棵只有根节点的树，根编号为0，根有两个点权p0和w0；
在q 个操作中，每个操作是以下三种情况之一：
• 操作1：新增一个未出现过的节点u，令节点u与某已经存在的节点v相连，有两个点

权pu 和wu，保证pu<pv；

• 操作2：进行一次询问，给定节点k 和背包容量s，查询从节点k 到根的路径点集X 中，给每个点v∈X分配一个非负整数mv，在约束(∑mv≤s)∧(mv≤wv),v∈X 下， 得到Ans=max∑ v∈X(mv×pv)，输出 ∑mv 和 Ans，注意每次询问过后，需要进行更 新wv =wv−mv； 

• 操作3：给定一个节点l，将wl 置为0.



输入格式

第一行输入一个正整数T(1≤T ≤10)，表示有T 组测试用例。对每组测试用例：
• 第一行，给出三个整数q,p0,w0，以空格隔开，分别表示总天数，根节点农田农作物营
养值，农作物重量。
• 接下来q行，首先给出一个整数opt，用于表示三种事情的编号，紧接一个空格，然后
根据opt 的不同：
• 若opt=1，则表示发现新的农田，接下来给出整数u,v,pu,wu，同样以空格隔开，保证
编号为u的农田未被发现，而为v的已被发现，且pu<pv；
• 若opt=2，则表示回家整理行装，接下来给出整数k,s，同样以空格隔开，保证编号k
的农田已经被发现，此时需要进行输出，具体见“输出格式”节；
• 若opt=3，则表示异变蝗虫入侵，接下来给出整数l，同样保证编号l的农田已经被发
现。
对所有测试用例，1≤q≤2×105，且1≤u≤2×105，0≤v,k,l≤2×10^5，0≤pi,wi,s≤
 10^6, i ∈ N。

输出格式

对每组测试用例：若输入opt为2，则需要输出一行两个整数x,y（用空格隔开），分别表示 背包中装入的农作物重量，以及能得到的粮食总量。

输入样例 复制 

1
5 6 4
2 0 3
1 2 0 3 2
2 2 4
1 4 0 1 3
2 4 2

输出样例 复制 

3 18
3 12
2 2

数据范围与提示

在样例中，一共有q=5天，初始根节点p0=6,w0=4.
 • 第一天，用大小为s=3的背包容量，拿走了0号节点3个单位重量的农作物，w0→1，
得到粮食总量是3×6=18.
 • 第二天，添加了一个2号节点，连向0号点，p2=3<p0,w2=2.
 • 第三天，用大小为s=4的背包，在2号点询问，拿走0号点1个单位重量的农作物，以及
    2 号点2个单位重量的农作物，得到的总重量为1+2=3，粮食总量是1×6+2×3=12.
 • ...

分类标签