JOISC2018 Construction
Statement
给定 $n$ 个点，初始时 $i$ 号点的权值为 $c_i$。
接下来进行 $n-1$ 次加边操作，每次连接一条边 $(u,v)$，保证此时 $u$ 与 $1$ 号点连通，$v$ 与 $1$ 号点不连通。
对于每一次加边，求出 $1$ 号点到 $u$ 的简单路径上的逆序对数量，并在操作结束后将 $1$ 号点到 $u$ 的简单路径上的所有点的权值改为 $c_v$。
$1 \le n \le 10^5,1 \le c_i \le 10^9,1 \le u,v \le n$。
Solution
我不会 lct。最后的形态显然是树，可以考虑离线。
进行轻重链剖分后一条到根路径会分成最多 $\log n$ 条重链。
我们考虑从 $u$ 往上跳，可以用线段树维护每个节点的颜色，支持高效的查询，对于节点 $x$ 所在的极长连续段的顶端在哪。
直接暴力跳颜色段，计算该极长段长度，插入值域树状数组并统计答案即可。具体就是对于 $a_i>a_j,dep_i<dep_j$，令 $i$ 在此连续段。
染色和跳链的复杂度都是均摊 $O(\log n)$ 的，而树状数组也有 $O(\log n)$ 的复杂度。注意要记录插入了什么以方便高效清空树状数组。
总时间复杂度 $O(n\log^2n)$。
核心跳颜色段代码：
ll solve(int u){
ll rt=0;
while(u){
int col=query(1,1,n,dfn[u]),pos=max(dfn[top[u]],query(1,1,n,dfn[u],col)+1);
int len=dfn[u]-pos+1;
rt+=1ll*bit::query(col-1)*len;
bit::add(col,len);
if(pos==dfn[top[u]]) u=fa[top[u]];
else u=rev[pos-1];
}
bit::clear();
return rt;
}
另解（我不会）
某大神说：
颜色段在树上可以考虑 LCT。
在本题也很可做。