这题网上题解比较少……

于是本蒟蒻就来写一发吧

~~~~~吐槽时间~~~~~

这种题属于太弱布吉岛，普通人不会做，太神更不做的题目……

Katharon#1题解中似乎讲的蛮详细的，不过我是自己YY的……

因为提前被剧透是Splay+LCT，于是本蒟蒻看了半天布吉岛那个据点顶个鸟用，题解表示，我这是给你们降低难度！

或许是为了减小常数？不过BZOJ上无压力~

不开long long毁一生

~~~~~吐槽时间结束~~~~~

首先我们把那个据点扔到一边，直接解决更难的问题，任意选两个点，翻转它们之间的权值

因为我们要翻转路径权值，所以显然需要一个Splay

(Treap不行？均摊分析会跪吧……)

然后用什么维护外层呢？

树链剖分？不行，因为我们需要提取一点路径

那就LCT了！

有LCT还要神马Splay，直接翻转不就好？您这样翻转的是一条链……

此处我们再围观一下LCT

LCT是用一堆Splay维护链剖分，每个链以深度为关键字用Splay维护起来，链的Splay的根上记录着它的父亲，即树链剖分中的pre[top[x]]

然后我们定义

splay(x)：操作完之后使得x为所在链的Splay的根

access(x)：操作完之后使得x在主链且x在链尾，即只提取root和x之间的路径

reroot(x)：操作完之后使得x在主链且x在链首，即让x变为根

因为不同的LCT实现可能不同，所以我们这里的操作按这个定义来实现(学过LCT的就可以按这个要求实现)

然后另外的Splay在哪里？我们把它记录在一条链的根节点上，上面维护着这条链对应的Splay的根节点(同样以深度为关键字，所以是一一对应的，当然，深度不需要在程序中体现)

splay操作是基本，我们先解决它

注意到只有根节点上记录的对应Splay节点是有效的，所以我们只需要在最后一步rotate时将根节点的值赋给x就好了

因为借助access和reroot，我们可以实现提取链的功能，接下来只要解决这两个，这题就做完了

因为显然reroot(x)=access(x)+reverse(x)，所以我们只需要解决reverse，解决方案很显然，把对应的Splay也翻转一遍就是了(所以说Splay也是以深度为关键字)

然后就是access了

access的代码可以是这样 for (cut(p);p->pre!=null;splay(p)) cut(p->pre), p->pre->ch[1]=p, link(p->pre);

当然，对于最普通的LCT操作，cut(p)=splay(p) link(p)={};

以下操作大方针：时刻保证链的根节点记录的对应Splay节点也是根

在这里就有些不同了，cut/link的同时，会导致根节点的记录节点有变化，什么变化呢？

cut的变化是删除了右儿子的一部分并将那部分赋给右儿子(右儿子也成为了链的根节点)

对应到Splay当中就是split操作，不过从哪split呢？在LCT上记录一个size就可以解决

link的变化是增加了右儿子的一部分，对应到Splay当中就是merge操作

因为本题接下来就是Splay和LCT的姿势问题，所以代码自行YY吧~

BZOJ3159:决战