Submission #170513

---

Source Code Expand

#include <iostream>
#include "../Util/MyAssert.hpp"
#define assert my_assert

//Top Tree
//論文: <http://arxiv.org/abs/cs.DS/0310065>
//スライド: <http://www.cs.princeton.edu/~rwerneck/docs/TW05_p.pdf>
//実装: <https://github.com/katox/toptree/>
//アイデア自体はそこまで複雑でも無いと思うのだけれど、シンプルに実装できるものなのだろうか？

/*
・辺のcircular orderはとりあえず無視
・単にlink-cut treeで子ノードを平衡木で管理するような感じじゃだめなのかな…？
・パスを連結するのはパスのheadでなくて常にpath local treeの根がなる。
	parentの関係とか木に対するクエリとかを考えればこうじゃないとだめだと思う。
・headの方向が左とする
*/

#include <cstdio>
#include <set>

class DynamicTree {
public:
	struct Node {
		Node *pathLeft, *pathRight;			//path local tree
		Node *siblingLeft, *siblingRight;	//sibling local tree
		Node *topChild;						//path local treeからsibling local treeへ
		Node *parent;						//path/sibling local treeの両方で用いられる

		Node()
			: pathLeft(NULL), pathRight(NULL)
			, siblingLeft(NULL), siblingRight(NULL)
			, topChild(NULL), parent(NULL)
			{ }

		inline Node *&path(bool lr) { return !lr ? pathLeft : pathRight; }
		inline Node *&sibling(bool lr) { return !lr ? siblingLeft : siblingRight; }
		inline Node *&child(bool ps, bool lr) { return !ps ? path(lr) : sibling(lr); }

		inline bool isLocalRoot(bool ps) const {
			return !parent || (parent->child(ps, false) != this && parent->child(ps, true) != this);
		}
	};

private:
	static void rotate(Node *a, bool ps, bool lr) {
		Node *p = a->parent, *g = p->parent, *c = a->child(ps, lr);
		if(p->child(ps, !lr) = c) c->parent = p;
		a->child(ps, lr) = p; p->parent = a;
		if(a->parent = g) {
			if(g->pathLeft == p) g->pathLeft = a;
			else if(g->pathRight == p) g->pathRight = a;
			else if(g->siblingLeft == p) g->siblingLeft = a;
			else if(g->siblingRight == p) g->siblingRight = a;
			else if(g->topChild == p) g->topChild = a;
		}
	}

	static void localSplay(Node *a, bool ps) {
		while(!a->isLocalRoot(ps)) {
			Node *p = a->parent;
			bool plr = p->child(ps, true) == a;
			if(p->isLocalRoot(ps)) {
				rotate(a, ps, !plr);
			}else {
				Node *g = p->parent;
				bool glr = g->child(ps, true) == p;
				if(plr == glr) {
					rotate(p, ps, !plr);
					rotate(a, ps, !plr);
				}else {
					rotate(a, ps, glr);
					rotate(a, ps, plr);
				}
			}
		}
	}
	
	static Node *pathHead(Node *a) {
		assert(a->isLocalRoot(false));
		Node *h = a;
		while(h->pathLeft) h = h->pathLeft;
		localSplay(h, false);
		return h;
	}

	static void splitPath(Node *a) {
		assert(a->isLocalRoot(false));
		Node *r = a->pathRight, *c = a->topChild;
		if(r != NULL) {
			a->pathRight = NULL;
			a->topChild = r;
			assert(r->siblingLeft == NULL && r->siblingRight == NULL);
			if(r->siblingLeft = c) c->parent = r;
		}
	}

	//sibling local tree上でaを削除する(切り離す)。aはsplayされている必要がある
	static void deleteChild(Node *a) {
		Node *r = a->siblingLeft;
		if(!r) {
			if(r = a->siblingRight) r->parent = a->parent;
			if(a->parent) a->parent->topChild = r;
		}else {
			while(r->siblingRight) r = r->siblingRight;
			localSplay(r, true);
			assert(r->siblingRight == a && !a->siblingLeft);
			Node *b = a->siblingRight;
			if(r->siblingRight = b) b->parent = r;
		}
		a->siblingLeft = a->siblingRight = NULL;
	}

public:
	static void expose(Node *a) {
		while(true) {
			localSplay(a, false);
			localSplay(a, true);
			Node *p = a->parent;
			if(!p) break;
			assert(p->topChild == a);
			Node *h = pathHead(a);
			assert(p->topChild == h);
			//spliceする。パスの頭(h)とパスの親(p)を接合する。pの下側は切り離される
			localSplay(p, false);
			Node *r = p->pathRight;
			p->pathRight = h;	//意味は変わってもpがhのparentであることは変わらない
			if(r != NULL) {
				p->topChild = r;	//同様に、pがrのparentであることも変わらない
				if(r->siblingLeft = h->siblingLeft) r->siblingLeft->parent = r;
				if(r->siblingRight = h->siblingRight) r->siblingRight->parent = r;
				h->siblingLeft = h->siblingRight = NULL;
			}else {
				deleteChild(h);
			}
		}
	}

public:
	static void directedLink(Node *a, Node *p) {
		expose(a);
		assert(a->parent == NULL);
		Node *c = p->topChild;
		p->topChild = a;
		a->parent = p;
		if(a->siblingLeft = c) c->parent = a;
	}

	static void directedCut(Node *a) {
		expose(a);
		Node *l = a->pathLeft;
		assert(l != NULL);
		a->pathLeft = NULL;
		l->parent = NULL;
	}

	static Node *lca(Node *a, Node *b) {
		expose(a);
		splitPath(a);
		Node *ah = pathHead(a);
		expose(b);
		splitPath(b);
		Node *bh = pathHead(b);
		if(ah != bh) return NULL;
		while(1) {
			localSplay(a, false);
			if(!a->parent) return a;
			localSplay(a, true);
			a = a->parent;
		}
	}

	static void debugCheck(const Node *a, std::set<const Node*> &visited) {
		if(visited.count(a)) return;
		const Node *root = a;
		while(root->parent) {
			root = root->parent;
			assert(!visited.count(root));
		}
		debugCheckRec(root, NULL, visited);
	}

	static void debugCheckRec(const Node *a, const Node *p, std::set<const Node*> &visited) {
		assert(!visited.count(a));
		visited.insert(a);
		assert(a->parent == p);
		if(a->siblingLeft != NULL || a->siblingRight != NULL) {
			assert(a->isLocalRoot(false));
			assert(p != NULL && (p->topChild == a || p->siblingLeft == a || p->siblingRight == a));
		}
		if(p == NULL || (p->topChild == a || p->siblingLeft == a || p->siblingRight == a))
			assert(a->isLocalRoot(false));
		if(p == NULL || p->topChild == a)
			assert(a->isLocalRoot(true));
		if(a->pathLeft) debugCheckRec(a->pathLeft, a, visited);
		if(a->pathRight) debugCheckRec(a->pathRight, a, visited);
		if(a->topChild) debugCheckRec(a->topChild, a, visited);
		if(a->siblingLeft) debugCheckRec(a->siblingLeft, a, visited);
		if(a->siblingRight) debugCheckRec(a->siblingRight, a, visited);
	}
};


int main() {
	using std::scanf;
	using std::printf;
	typedef DynamicTree::Node Node;
	static Node nodes[1000000];
	int N, Q;
	scanf("%d%d", &N, &Q);
	for(int ii = 0; ii < Q; ii ++) {
		int T;
		scanf("%d", &T);
		if(T == 1) {
			int A, B;
			scanf("%d%d", &A, &B);
			A --, B --;
			DynamicTree::directedLink(&nodes[A], &nodes[B]);
		}else if(T == 2) {
			int A;
			scanf("%d", &A);
			A --;
			DynamicTree::directedCut(&nodes[A]);
		}else if(T == 3) {
			int A, B;
			scanf("%d%d", &A, &B);
			A --, B --;
			Node *l = DynamicTree::lca(&nodes[A], &nodes[B]);
			if(l == NULL) puts("-1");
			else printf("%d\n", (int)(l - nodes + 1));
		}
//		std::set<const Node*> visited;
//		for(int i = 0; i < N; i ++)
//			DynamicTree::debugCheck(&nodes[i], visited);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp:2:32: fatal error: ../Util/MyAssert.hpp: No such file or directory
compilation terminated.