当前位置: 首页 > news >正文

2025十一集训——Day1做题

题单

A

咕咕咕

B

咕咕咕

C

咕咕咕

D春节十二响

vjudge

luogu

(Day -1 过的qwq)

题意:一棵树,节点有点权,将节点分成任意个集合,要求每个集合内的节点不是祖先——后代关系,问(每个集合中的(点的最大值)之和)最小是多少。

很妙的启发式合并。

考虑如果这是个链而且根左右两条小链,显然可以将两边的链各扔进一个堆,每次取堆首,并加上两者较大值(感性理解,用一边最大的消耗另一边的最大,是贡献最少)。

然后扩展到树上,每个点开一个堆,这就叫树上启发式合并。

现在还不行,因为这东西会被卡成 \(O(n^2\log n)\)

然后才是启发式的常用 trik:

将子树大小小的往大的里插。

这东西就类似于树剖那个重儿子,直接把 \(O(n^2)\) 变成 \(O(n\log n)\)

而且代码只需加一行:

点击查看代码
if (q[id[u]].size() < q[id[v]].size()) swap(id[u], id[v]);

然后得到了启发式合并

哦哦下标那里有个 trik,是说我们要交换两个堆,直接换是 \(O(\text {size})\) 的,但是可以每个点存个对应堆的下标,然后直接换下标……

做完了……

点击查看代码
#include <bits/stdc++.h>
#define dbg(x) cout << #x << '=' << x << endl
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define frep(i, r, l) for (int i = (r); i >= (l); i--)
#define int long long
using namespace std;const int N = 2e5 + 10;int n, cnt;
int a[N], id[N];
vector<int> e[N];
priority_queue<int> q[N];
int b[N], pos;int Get(int x) {int p = q[x].top();q[x].pop(); return p;
}void Dfs(int u) {id[u] = ++cnt;int ax, ay;for (int v : e[u]) {Dfs(v);if (q[id[u]].size() < q[id[v]].size()) swap(id[u], id[v]);pos = 0;while (!q[id[v]].empty()) b[++pos] = max(Get(id[u]), Get(id[v])); rep(j, 1, pos) q[id[u]].push(b[j]);}q[id[u]].push(a[u]);
}void work()
{cin >> n;rep(i, 1, n) cin >> a[i];rep(i, 2, n) {int f; cin >> f;e[f].push_back(i);}Dfs(1);int sum = 0;while (!q[id[1]].empty()) sum += Get(id[1]);cout << sum << "\n";
}signed main()
{std::ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1, opinput = 0;if (opinput) cin >> T;while (T--) work();return 0;
}

其实没什么大结论的题,感觉比较板……

希望能场切 这种吧。

E

咕咕咕

F

咕咕咕

G

咕咕咕

H

咕咕咕

I

咕咕咕

http://www.hskmm.com/?act=detail&tid=22711

相关文章:

  • AI元人文:价值共生体系统——构建人机文明的演进基石
  • 2025.9.30 刷题
  • 荣耀毕业了
  • “掐尖招生”终于引起高层的警觉
  • 汽车央企“哄抢”华为
  • CF2150D
  • AI元人文:致同行者书
  • tp5 基础nginx伪静态
  • 异或运算的一个小等式
  • AI元人文:“现实与价值”的生态——走向一种基于博弈与演化的协同智能
  • 169. 多数元素
  • Ai元人文:最后的客观与乐观
  • AI元人文:价值原语构想——迈向动态博弈的价值生态
  • 《多分支条件判断优化:switch-case 结构的技术价值分析》
  • Codeforces 1385G Columns Swaps 题解 [ 蓝 ] [ 扩展域并查集 ] [ 二分图最大权匹配 ] [ 基环树建模 ]
  • 72. 编辑距离
  • PlantUML 完整教程:从入门到精通
  • 你妈的
  • test6
  • test7
  • 学习java的第三天
  • vscode github 推送失败
  • 信奥大联赛周赛(提高组)#2515-S 赛后盘点
  • 虚拟机仅主机模式下使用ssh远程连接Linux(EHEL8)连接慢,需要等待30秒以上
  • VLC Player插件和自动激活
  • 第七天
  • logback.xml 常用配置详解 - Higurashi
  • MySQL COUNT(*)性能对比:MyISAM为何比InnoDB快?全面解析与优化方案
  • 2025.10.1总结
  • 子结构判断