Codeforces Round #821 (Div. 2)
2022/9/14 6:19:06
本文主要是介绍Codeforces Round #821 (Div. 2),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
Codeforces Round #821 (Div. 2)
D.Fake Plastic Trees
\(t\) 组数据,每组给定一个 \(n\) 个结点的树, 根为 \(1\) ,给定 \(2,3,\ldots ,n\) 的父结点 \(p_2,p_3,\ldots ,p_n\) 。再给出每个点权值 \(a_i\) 的范围 \([l_i,r_i]\) 。
初始每个点的权值均为 \(0\) 。每次操作可以选择从 \(1\) 开始的树上路径 \(b_1,b_2,\ldots,b_k\) (不一定要在叶子处结束),将 \(a_{b_i}\) 加上 \(c_i\) ,其中 \(\{c_i\}\) 是一个 非负单调非减 的 整数 数列。
问至少多少次操作,可以令所有点点权均在 \([l_i,r_i]\) 范围内。
\(1\le t\le 1000,2\le n\le 2\times 10^5,\sum n\le 2\times 10^5,1\le p_i<i,1\le l_i\le r_i\le 10^9\)
解题思路
贪心
贪心策略:从叶子节点开始尽量消最多,关键在于 \(dfs\) 的写法
- 时间复杂度:\(O(n)\)
代码
// Problem: D. Fake Plastic Trees // Contest: Codeforces - Codeforces Round #800 (Div. 2) // URL: https://codeforces.com/contest/1694/problem/D // Memory Limit: 256 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) // %%%Skyqwq #include <bits/stdc++.h> // #define int long long #define help {cin.tie(NULL); cout.tie(NULL);} #define pb push_back #define fi first #define se second #define mkp make_pair using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; } template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; } template <typename T> void inline read(T &x) { int f = 1; x = 0; char s = getchar(); while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); } while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar(); x *= f; } const int N=2e5+5; int t,n,res,b[N]; PII a[N]; bool v[N]; vector<int> adj[N]; void dfs(int x) { LL s=0; for(int y:adj[x]) { dfs(y); s+=b[y]; } if(a[x].fi>s)res++,b[x]=a[x].se; else b[x]=min(1ll*a[x].se,s); } int main() { for(cin>>t;t;t--) { cin>>n; for(int i=1;i<=n;i++)adj[i].clear(),b[i]=0; for(int i=2;i<=n;i++) { int x;cin>>x; adj[x].pb(i); } for(int i=1;i<=n;i++)cin>>a[i].fi>>a[i].se; res=0; dfs(1); cout<<res<<'\n'; } return 0; }
这篇关于Codeforces Round #821 (Div. 2)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-04安装 VPrix Desktop 的系统要求-icode9专业技术文章分享
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享