https://codeforces.com/contest/1099/problem/F 题意 一颗n个节点的树上,每个点都有/(x[i]/)个饼干,然后在i节点上吃一个饼干的时间是/(t[i]
... .
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,v);}ll qy(int o,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,lt-sum[o<<1]); return qy(o<<1,lt);}void dfs(int u,ll lt){ if(lt<=0)return; ud(1,1,m,t[u],x[u]); dp[u]=qy(1,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,-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];} . .. ...
