Nuartz

notes

Search

Search IconIcon to open search

top-tree実装体験木

Last updated Jun 29, 2019

読者層が限定されすぎていませんか？

Link Cut Treeを書いたことがない人はこちら！

Link-Cut 木 - ei1333の日記

部分木クエリについてはこちら！

Link Cut Treeで部分木の情報を管理する - beet's soil

最遠点クエリについてはこちら！

Link-Cut木と最遠点クエリ - ei1333の日記

え〜っと, 多分toptreeが書けました. 多分! verifyしたいんですが, Rustのバージョンで困っています…

# 実装

論文を読むとかける！(素振り) 間違ってたらごめんなさい

LinkCutTreeがならしO(logN)らしいし, これもO(logN)だと信じている(解析できねえ…)

# 読んだもの

# toptree?

LinkCutTreeでは, Heavy-edgeのパスを頂点の順番でSplayTreeで管理していました. また, 上のLinkCutTreeでの部分木クエリでは, Light-edgeでつながったものを, multisetで管理しています.

これを, Heavy-edgeのパスを辺の順番で, 辺を葉とするSplayTreeで管理し, Light-edgeでつながったものをSplayTreeでまとめたデータ構造が, TopTreeの雑な説明です. このSplayTreeにクエリを処理させれば, 部分木クエリなどができます. link, cutもできます.

ここでもっと雑な説明をしてしまうとTopTreeが分からなくなってしまいそうなので, 他の記事にゆっくりまとめたいと思います… まとめる時間をください…(学業がなくなれば)

# 実際にできたクエリ

TopTreeにはClusterを載せてクエリを処理させます. ClusterのTraitは以下のようになっています.

1
2
3
4
5
6

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パスの長さ

1
2
3
4
5
6

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を定義すると

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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);
}

# 木の直径クエリ

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#[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を定義すると

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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の直径のやつ適当にいくつか通しました(提出できない)

# 最遠点クエリ

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#[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を定義すると

J - 仕事をしよう！ (Working!)

が解けます. サンプルは通りました(AtCoderさんverifyさせてくださいおねがいします)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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はまだやってない.

何が載るのかはさっぱりわかりません, だれか解明して.