题解
7 分钟 读完 (大约 1024 个字)

胡闹 方差

题目大意

维护一颗$n\le10^5$个点的树，每个点有颜色$c_i\le10^5$。

初始时只有$1$号节点。

三种操作：

  1. 加入一个点，给定它的编号、颜色和父亲。
  2. 询问路径$(x,y)$上的所有点。
  3. 询问点$x$的子树内的所有点（以$1$为根）。

询问的意思是说，把所有的点的颜色去重求方差。

阅读更多
题解
6 分钟 读完 (大约 923 个字)

Luogu 4074 [WC2013 糖果公园]

传送门

正确性什么的先咕咕咕一下吧，我也不太会。

题目大意

有一个$n\le10^5$个节点的树，每个节点有一个颜色。

每次询问：
$$
\sum_cval_c\times\sum_{i=1}^{cnt}w_i
$$
$val_c$表示该颜色的价值

$cnt$表示颜色出现的次数

$w_i$表示该颜色出现$i$次后的价值

带修改。

阅读更多

链接

分类

标签云

AC自动机 FFT、NTT Hash K-D Tree Kruskal重构树 SAM WO YE BU HUI excrt lct 主席树 二分图 交互 倍增 卡常 可并堆 可持久化 坑 多项式 套路 字符串 容斥 左偏树 带修莫队 平衡树 技巧 插头dp 数论 斜率优化 树上莫队 树套树 毒瘤计数 生成函数 网络流 胡闹系列 莫比乌斯反演 计算几何 高级数据结构 黑科技

最新文章

归档

标签

AC自动机 1
FFT、NTT 6
Hash 3
K-D Tree 1
Kruskal重构树 1
SAM 4
WO YE BU HUI 7
excrt 1
lct 2
主席树 4
二分图 2
交互 1
倍增 2
卡常 2
可并堆 1
可持久化 1
坑 2
多项式 1
套路 2
字符串 10
容斥 2
左偏树 1
带修莫队 2
平衡树 2
技巧 5
插头dp 1
数论 5
斜率优化 2
树上莫队 2
树套树 5
毒瘤计数 2
生成函数 1
网络流 4
胡闹系列 18
莫比乌斯反演 3
计算几何 3
高级数据结构 11
黑科技 2
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×