Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

05/12
09:56
线段树

[bzoj 4551] Tjoi2016&Heoi2016 树

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

在2016年,佳媛姐姐刚刚学习了树,非常开心。现在他想解决这样一个问题:给定一颗有根树(根为1),有以下两种操作:1. 标记操作:对某个结点打上标记(在最开始,只有结点1有标记,其他结点均无标记,而且对于某个结点,可以打多次标记。)2. 询问操作:询问某个结点最近的一个打了标记的祖先(这个结点本身也算自己的祖先)你能帮帮他吗?

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

输入第一行两个正整数N和Q分别表示节点个数和操作次数接下来N-1行,每行两个正整数u,v(1≤u,v≤n)表示u到v有一条有向边接下来Q行,形如“opernum”oper为“C”时表示这是一个标记操作,oper为“Q”时表示这是一个询问操作对于每次询问操作,1 ≤ N, Q ≤ 100000。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

输出一个正整数,表示结果

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

5 5
1 2
1 3
2 4
2 5
Q 2
C 2
Q 2
Q 5
Q 3

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

1
2
2
1

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

把dfs序搞出来然后乱搞

标记就是把标记的节点的子树(一段区间)用这个点来更新一下 查询就是查询某个点的答案

c++:

pascal:

 

[bzoj 4551] Tjoi2016&Heoi2016 树