Codeforces Round #530 (Div. 2) F 线段树 + 树形dp(自下往上)
2024-08-30 09:40:21
https://codeforces.com/contest/1099/problem/F
题意
一颗n个节点的树上,每个点都有\(x[i]\)个饼干,然后在i节点上吃一个饼干的时间是\(t[i]\),有n-1条边,每条边有边权w为经过一条边所需时间,你从树根开始先手向下走,然后对手割掉你所在节点到子节点的任意一条边,你可以在任何时间选择返回,在返回的过程中你可以选择性吃掉经过节点的饼干,问在双方最优的情况下,你最多能在T时间之内吃掉多少饼干并返回根节点(在足够时间返回根节点的情况下吃掉尽可能多的饼干)
题解
- 对于选择哪个子节点对于双方最优,只有到最后一层节点(叶子)才知道,所以需要从下往上解决问题
- 定义dp[u]为经过节点u并能返回根最多能吃多少饼干,
- u为根,\(dp[u]=max(dp[v])\)
- u不为根,\(dp[u]=max2(dp[v])\),选择第二大,因为最大被对手割掉
- u为叶子,dp[u]为剩下时间lt,所能吃掉的最多的饼干数量
- dp[1]为答案
- 权值线段树(时间为x轴)维护路径上能吃的饼干数量num以及所需时间sum,因为到叶子的时候整条路径的饼干情况都标记在线段树上,而一定是从时间小(贪心)的开始吃,所以可以很方便找到sum<=lt最大的num,线段树起了一个类似标记数组的作用
代码
#include<bits/stdc++.h>
#define MAXN 1000005
#define m 1000000
#define ll long long
#define mk make_pair
#define ft first
#define se second
#define pii pair<int,int>
using namespace std;
vector<pii>G[MAXN];
ll sum[MAXN<<2],num[MAXN<<2],T;
int dp[MAXN],t[MAXN],x[MAXN];
int n,u,w;
void ud(int o,int l,int r,int p,int v){
sum[o]+=1ll*p*v;num[o]+=v;
if(l==r)return ;
int mid=(l+r)/2;
if(p<=mid)ud(o<<1,l,mid,p,v);
else ud(o<<1|1,mid+1,r,p,v);
}
ll qy(int o,int l,int r,ll lt){
if(sum[o]<=lt)return num[o];
if(l==r)return lt/l;
int mid=(l+r)/2;
if(lt>=sum[o<<1])return num[o<<1]+qy(o<<1|1,mid+1,r,lt-sum[o<<1]);
return qy(o<<1,l,mid,lt);
}
void dfs(int u,ll lt){
if(lt<=0)return;
ud(1,1,m,t[u],x[u]);
dp[u]=qy(1,1,m,lt);
int mx1=0,mx2=0;
for(auto tp:G[u]){
int v=tp.ft,w=tp.se;
dfs(v,lt-2*w);
if(dp[v]>mx1){mx2=mx1;mx1=dp[v];}
else if(dp[v]>mx2){mx2=dp[v];}
}
if(u==1)dp[u]=max(dp[u],mx1);
else dp[u]=max(dp[u],mx2);
ud(1,1,m,t[u],-x[u]);
}
int main(){
cin>>n>>T;
for(int i=1;i<=n;i++)scanf("%d",&x[i]);
for(int i=1;i<=n;i++)scanf("%d",&t[i]);
for(int i=2;i<=n;i++){
scanf("%d%d",&u,&w);
G[u].push_back(mk(i,w));
}
dfs(1,T);
cout<<dp[1];
}
最新文章
- java中内存分配策略及堆和栈的比较
- 数据库访问CRUD;__SELF__和__ACTION__的区别;自动收集表单:$n->;create();
- [Java 基础] 并发队列ConcurrentLinkedQueue和阻塞队列LinkedBlockingQueue用法
- 解决IE11出现异常SCRIPT5011:不能执行已释放Script的代码
- 解决IE不支持position:fixed问题
- [LeetCode] 42. Trapping Rain Water 解题思路
- CSS简要内容
- aix vg lv pv
- BON取代半岛电视,美国人要“换口味”了吗?
- python绝技 — 用Scapy解析TTL字段的值
- n皇后问题 [随机化算法,拉斯维加斯算法]
- Javascript删除数组中指定值的元素
- Python 操作 MYSQL
- 【java】对象克隆protected Object clone() throws CloneNotSupportedException
- css变量的用法——(--cssName)
- iOS.Animations.by.Tutorials.v2.0汉化(四)
- C#根据屏幕分辨率改变图片尺寸
- C# DataConstruct 数据结构关于 Array,ArrayList,List,HashTable,Dictionnary的学习记录
- RSA签名的PSS模式
- 《python for data analysis》第五章,pandas的基本使用
热门文章
- python-9-列表的增删改查
- $.Ajax、$.Get、$.Post代码实例参数解析
- Window权限维持(九):端口监视器
- java架构之路(mysql底层原理)Mysql之Explain使用详解
- Swagger实例分享(VS+WebApi+Swashbuckle)
- U盘安装CentOS 7提示 “Warning: /dev/root does not exist, could not boot” 解决办法
- Python-函数参数类型及排序问题
- centos7安装mysql5.7(rpm安装版)
- 原生JavaScript HTML DOM Style 对象参考
- vue中嵌套的iframe中控制路由的跳转及传参