某岛

… : "…アッカリ~ン . .. . " .. .
November 6, 2012

POJ 3237. Tree

Brief description:

动态维护一颗点权树,要求支持以下操作:

  • INSERT T: 插入、在节点 T 下新增一个节点
  • CUT S T: 切掉、切掉以节点 S 为根的子树,接到节点 T 上。
  • CHANGE T D: 单点修改、将节点 T 修改为 D。
  • ADD T D: 子树修改、将以 T 为根的子树中所有结点增加 D。
  • QMAX T: 子树最值、询问以 T 为根的子树中所有结点的最大权值。
  • QSUM T: 子数和、询问以 T 为根的子树中所有结点的权值和。

初始是只有 1 个编号为 1 的节点,权值为 0,对于插入 (INSERT) 操作,结点的权值默认为 0,对于链接 (CUT) 操作,如节点 T 在以节点 S 为根的子树中,则忽略。
(总操作数 <= 200000。。)

Analysis:

这我哪会做呀。。=w=。。

External link:

http://poj.org/problem?id=3237
http://www.baidu.com/s?tn=baiduhome_pg&ie=utf-8&bs=POJ+tree+splay+%E7%BB%B4%E6%8A%A4+dfs+%E5%BA%8F%E5%88%97&f=8&rsv_bp=1&rsv_spt=1&wd=POJ+3237&rsv_sug3=3&rsv_sug1=3&rsv_sug4=113&inputT=1904
https://www.google.com.hk/#hl=zh-CN&newwindow=1&safe=strict&site=&source=hp&q=POJ+3237&oq=POJ+3237&gs_l=hp.13..0i30.843.843.0.1808.1.1.0.0.0.0.102.102.0j1.1.0…0.0…1c.1.xy-wmHCYlcY&bav=on.2,or.r_gc.r_pw.r_cp.&fp=e59225bfc82899a5&bpcl=37189454&biw=1680&bih=925