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] 三块。。。左右两块切出去以后再链接上。。。
（..我发现 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 函数刚开始的时候给她赋值。。。
