top-tree実装体験木
読者層が限定されすぎていませんか？
Link Cut Treeを書いたことがない人はこちら！
部分木クエリについてはこちら！
最遠点クエリについてはこちら！
え〜っと, 多分toptreeが書けました. 多分! verifyしたいんですが, Rustのバージョンで困っています...
実装
論文を読むとかける！(素振り) 間違ってたらごめんなさい
LinkCutTreeがならしO(logN)らしいし, これもO(logN)だと信じている(解析できねえ...)
読んだもの
- Maintaining Information in Fully-Dynamic Trees with Top Trees
- Design and Analysis of Data Structures for Dynamic Trees
- noshi91さんのツイート
toptree?
LinkCutTreeでは, Heavy-edgeのパスを頂点の順番でSplayTreeで管理していました. また, 上のLinkCutTreeでの部分木クエリでは, Light-edgeでつながったものを, multisetで管理しています.
これを, Heavy-edgeのパスを辺の順番で, 辺を葉とするSplayTreeで管理し, Light-edgeでつながったものをSplayTreeでまとめたデータ構造が, TopTreeの雑な説明です. このSplayTreeにクエリを処理させれば, 部分木クエリなどができます. link, cutもできます.
ここでもっと雑な説明をしてしまうとTopTreeが分からなくなってしまいそうなので, 他の記事にゆっくりまとめたいと思います... まとめる時間をください...(学業がなくなれば)
実際にできたクエリ
TopTreeにはClusterを載せてクエリを処理させます. ClusterのTraitは以下のようになっています.
pub trait Cluster: Clone { fn identity() -> Self; fn compress(left: Self, right: Self) -> Self; fn rake(left: Self, right: Self) -> Self; fn reverse(&mut self); }
v-uパスの長さ
impl Cluster for usize { fn identity() -> Self { 0 } fn compress(left: Self, right: Self) -> Self { left + right } fn rake(a: Self, _: Self) -> Self { a } fn reverse(&mut self) {} }
というふうにClusterを定義すると
pub fn path_length_test() { println!("path_length"); let v: Vec<_> = (0..13).map(|i| Vertex::new(i)).collect(); let edges = [ (0usize, 1usize, 1usize), (1, 2, 10), (1, 3, 3), (1, 4, 4), (0, 5, 3), (5, 9, 4), (9, 10, 7), (10, 11, 9), (10, 12, 1), (0, 6, 3), (6, 7, 3), (7, 8, 7), ]; let mut es = Vec::new(); for (a, b, w) in edges.iter() { es.push(link(v[*a], v[*b], *w)); } assert!(path_query(v[1], v[0]) == 1); assert!(path_query(v[0], v[4]) == 5); assert!(path_query(v[1], v[9]) == 8); assert!(path_query(v[3], v[11]) == 27); assert!(path_query(v[6], v[12]) == 18); assert!(path_query(v[12], v[6]) == 18); assert!(path_query(v[2], v[4]) == 14); assert!(path_query(v[5], v[6]) == 6); }
木の直径クエリ
#[derive(Clone, Debug)] struct Diameter { diam: usize, max_dist_left: usize, max_dist_right: usize, length: usize } impl Diameter { fn new(l: usize) -> Self { Diameter { diam: l, max_dist_left: l, max_dist_right: l, length: l, } } } impl Cluster for Diameter { fn identity() -> Self { Diameter { diam: 0, max_dist_left: 0, max_dist_right: 0, length: 0, } } fn compress(a: Self, b: Self) -> Self { Diameter { diam: *[ a.diam, b.diam, a.max_dist_right + b.max_dist_left].into_iter().max().unwrap(), max_dist_left: std::cmp::max(a.max_dist_left, a.length + b.max_dist_left), max_dist_right: std::cmp::max(b.max_dist_right, b.length + a.max_dist_right), length: a.length + b.length } } fn rake(a: Self, b: Self) -> Self { Diameter { diam: *[ a.diam, b.diam, a.max_dist_right + b.max_dist_right ].into_iter().max().unwrap(), max_dist_left: std::cmp::max(a.max_dist_left, a.length + b.max_dist_right), max_dist_right: std::cmp::max(a.max_dist_right, b.max_dist_right), length: a.length, } } fn reverse(&mut self) { std::mem::swap(&mut self.max_dist_left, &mut self.max_dist_right); } }
というふうにClusterを定義すると
pub fn diameter_cut_test() { println!("diameter cut"); let v: Vec<_> = (0..13).map(|i| Vertex::new(i)).collect(); let edges = [ (0usize, 1usize, 1usize), (1, 2, 10), (1, 3, 3), (1, 4, 4), (0, 5, 3), (5, 9, 4), (9, 10, 7), (10, 11, 9), (10, 12, 1), (0, 6, 3), (6, 7, 3), (7, 8, 7), ]; let mut es = Vec::new(); for (a, b, w) in edges.iter() { es.push(link(v[*a], v[*b], Diameter::new(*w))); } cut(v[0], v[5]); println!("0 diameter = {}", expose(v[0]).fold().diam); // -> 24 println!("5 diameter = {}", expose(v[5]).fold().diam); // -> 20 }
AOJの直径のやつ適当にいくつか通しました(提出できない)
最遠点クエリ
#[derive(Clone, Debug)] struct Farthest { ans: usize, max_dist_left: usize, max_dist_right: usize, length: usize } impl Farthest { fn new(l: usize) -> Self { Farthest { ans: l, max_dist_left: l, max_dist_right: l, length: l, } } } impl Cluster for Farthest { fn identity() -> Self { Farthest { ans: 0, max_dist_left: 0, max_dist_right: 0, length: 0, } } fn compress(a: Self, b: Self) -> Self { Farthest { ans: std::cmp::max(a.max_dist_right, b.max_dist_left), max_dist_left: std::cmp::max(a.max_dist_left, a.length + b.max_dist_left), max_dist_right: std::cmp::max(b.max_dist_right, b.length + a.max_dist_right), length: a.length + b.length } } fn rake(a: Self, b: Self) -> Self { Farthest { ans: 0, max_dist_left: std::cmp::max(a.max_dist_left, a.length + b.max_dist_right), max_dist_right: std::cmp::max(a.max_dist_right, b.max_dist_right), length: a.length, } } fn reverse(&mut self) { std::mem::swap(&mut self.max_dist_left, &mut self.max_dist_right); } }
というふうにClusterを定義すると
が解けます. サンプルは通りました(AtCoderさんverifyさせてくださいおねがいします)
pub fn farthest_test() { println!("farthest"); let mut buf = String::new(); std::io::stdin().read_to_string(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); let q: usize = iter.next().unwrap().parse().unwrap(); let mut v: Vec<_> = (0..1).map(|_| Vertex::new(())).collect(); let edges :Vec<(usize, usize, usize)>= (0..q).map(|_| { ( iter.next().unwrap().parse().unwrap(), iter.next().unwrap().parse().unwrap(), iter.next().unwrap().parse().unwrap(), ) }).collect(); let mut es = Vec::new(); for (t, a, c) in edges.iter() { if *t == 1 { let new_v = Vertex::new(()); v.push(new_v); link(v[*a], new_v, Farthest::new(*c)); es.push((*a, v.len() - 1)); } else if *t == 2 { let p = es[*a - 1].0; let q = es[*a - 1].1; cut(v[p], v[q]); link(v[p], v[q], Farthest::new(*c)); } else if *t == 3 { println!("farthest from {} = {}", *a, expose(v[*a]).fold().ans); } } }
Nearest Marked Vertex Queryはまだやってない.
何が載るのかはさっぱりわかりません, だれか解明して.
