bzoj 3653 谈笑风生 题解

Description

题目链接

设T 为一棵有根树,我们做如下的定义:

设a和b为T 中的两个不同节点。如果a是b的祖先,那么称“a比b不知道高明到哪里去了”。

设a 和 b 为 T 中的两个不同节点。如果 a 与 b 在树上的距离不超过某个给定常数x,那么称“a 与b 谈笑风生”。

给定一棵n个节点的有根树T,节点的编号为1 到 n,根节点为1号节点。你需要回答q 个询问,询问给定两个整数p和k,问有多少个有序三元组(a;b;c)满足:

  1. a、b和 c为 T 中三个不同的点,且 a为p 号节点;
  2. a和b 都比 c不知道高明到哪里去了;
  3. a和b 谈笑风生。这里谈笑风生中的常数为给定的 k。

Solution

分类讨论+dfs序+主席树

若$b$在$a$上方,$ans=min( dep[a]-1,k )\times ( sz[a] -1 )$

若$b$在$a$下方,主席树最外层$dfs$序,内层套线段树求区间和,维护子树大小。在$dep[a]+1$到$dep[a]+k$范围内求和$sz[TT]$。

Code

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇