「计蒜客模拟赛」抉择

Summarize

给定有根树，点有权值，要求选出一些点，满足集合中的点的祖先权值比它小，求集合大小的最大值。

$n\le 300000$

#48956. 「计蒜客模拟赛」魔法阵

Summarize

$n$ 个有编号的球放到有编号的环上，球分黑白两色，共 $k$ 个白球。要求至少有 $d$ 对黑球相邻，求方案数。

$n\le 1000000$

#T3252. 「计蒜客模拟赛」魔镜啊魔镜

Summarize

一棵 $n$ 个节点的树，给定 $m$ 个标记链。进行 $q$ 次询问，每次询问 $(u,v)$ 链上有多少条标记链。

$n\le 100000,m\le 100000,q\le 100000$

#T3253. 「计蒜客模拟赛」新年炸裂

Summarize

$n$ 个点、$m$ 条边的带权无向图，求从节点 $1$ 回到节点 $1$ 且不走回头路的最短路。

$n\le 10000,m\le 40000$

#T3244. 「计蒜客模拟赛」自适应平衡多叉处理数据结构

Summarize

维护数据结构，每次询问时执行 $O(\sqrt n)$ 次查询操作，每次修改执行一次修改操作。

$n\le 300000$

Summarize

给定 $n$ 种原材料，每种材料有一个特征值 $a_i$ 和强度 $b_i$。有 $q$ 次查询或修改，询问是给出一段区间 $[l,r]$，要求在 $l,l+1..r-1,r$ 的原材料中选出一个特征值线性无关的子集，是强度值之和最大；修改是修改某种原材料的特征值和强度。

$n\le 100000,q\le 10000,1\le a_i,b_i\le 1000000000$