Brief description:

。。。给定一棵 N 阶边权树，每次选择一条边拆开，输出当前边的权值。。。记作 w。。
。。并将拆开的两颗子树中，较小的一颗子树上的边全部 × w，较大子树的边全部 + w。。。
。。（ N <= 2e5, 强制在线。。）。。

Analysis:

… 前回 Southern Subregional Programming Contest 2012 的 Problem I。。
。。。。。。比赛时第一反应 dsu 倒着搞。。读到强制在线以后就 SB 了。。。。。 Euler Tour Tree 确实一次都没有写过。。（虽然就在前一天还在吃饭的时候和 二妹 讨论来着。。。
。。所以赛后就膜拜了一下 CLJ 的代码。。。发现这种非完全形态的 ETT 还是不难搞的。。。（既树的形态不发生改变。。没有换根。。

。。欧拉序列的每个位置都是伸展树的一个结点，难点是甩区间的时候。。。（这里由于最后都是一些小块。。而且引用的是区间位置。。也不太好直接在左右加 -oo 和 +oo 哨兵。。
（CLJ 这里的处理方法。。假设当前子树是 [a, b], 提取的区间是 [l, r] 。。则分成 [a, l-1] [l, r] [r+1, b] 三块。。。左右两块切出去以后再链接上。。。

（。。Euler Tour Tree。。。

（..我发现 CLJ 的伸展树 和 我的 同步率是很高的。。（比如我们都在类里面搞了一个函数判断是左孩子还是右孩子。。（我的是 sgn() 。。她的是 dir()。。。。

.. 然后看下面这段。。

void rot(Node*t) {
	Node*p = t->p;
	p->relax();
	t->relax();
	bool d = t->dir();
	p->p->setc(t, p->dir());
	p->setc(t->ch[!d], d);
	t->setc(p, !d);
	p->update();
}

void pushTo(Node*t) {
	static Node*stack[MAX_N * 2];
	int top = 0;
	while (t != null) {
		stack[top++] = t;
		t = t->p;
	}
	for (int i = top - 1; i >= 0; --i) {
		stack[i]->relax();
	}
}

void splay(Node*t, Node*f = null) {
	pushTo(t);
	while (t->p != f) {
		if (t->p->p == f)
			rot(t);
		else
			(t->dir() == t->p->dir()) ? (rot(t->p), rot(t)) : (rot(t), rot(t));
	}
	t->update();
}

（pushTo 疑似是 LCT 里面的操作。。可删。。。
。。然后 CLJ 这里的 rot 和 splay 函数是实现在外部的。。（。原因似乎是默认形参列表里面要用到哨兵 null。。
。。。。我的处理方法是在内部定义了一个 static node* NIL 。。。（然后在 mian 函数刚开始的时候给她赋值。。。

External link:

http://acm.sgu.ru/problem.php?contest=0&problem=550

Posted by xiaodao
Category: SGU
Tags: Euler Tour Tree