RainAir
My OI Blog
RainAir
「CF860E」Arkady and a Nobody-men

题目描述

给 $n$ 个节点的树。定义 $g(a,b)$ 表示 $a$ 的子树中除 $b$ 之外深度不超过 $b$ 的节点个数,定义 $f(v) = \sum_{x \in anc(v)} g(x,v)$ (其中 $anc(v)$ 是 $v$ 的祖先组成的集合)。
现在要对于每一个点,求出 $f(v)$
$n \leq 10^5$

题解

如果这题 $n \leq 10^5$ 那还是很 eazy 的。。可惜。。
首先我们对 $f(v)$ 求的东西做一个转化:我们考虑每个点 $i$ 只有在 $dep_i \leq dep_v$ 的时候会被贡献到,并且会被贡献 $dep_{lca(v,i)}$ 次。
也就是说 $f(v) = \sum_{dep_x \leq dep_v} dep_{lca(v,x)}$
我们分层考虑计算答案,发现每个节点会在它到根的路径上有贡献,查询节点的答案时只需要查询到根的和就好了(这样会在 lca 处被算到应该的次数),直接使用树链剖分。
但是这是两个 log,显然过不去。。
考虑我们每层的节点都按照 dfn 排序,现在计算这个点 $v$ 的答案,考虑如果转移到 dfn 更大的一个点 $v’$ 的时候,其他的点的 $dep$ 是单调不增的(最近的一段会变成现在的 lca,再往后就是之前的 lca)。我们可以用一个单调栈轻松维护。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/860
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

「CF860E」Arkady and a Nobody-men
题目描述 给 $n$ 个节点的树。定义 $g(a,b)$ 表示 $a$ 的子树中除 $b$ 之外深度不超过 $b$ 的节点个数,定义 $f(v) = \sum_{x \in anc(v)} g(x,v)$ (其中 $anc(v)$ 是 $v$ 的祖先组成的…
扫描二维码继续阅读
2019-10-09
标签
近期评论