P9867 [POI 2021/2022 R2] kon
Part. 0
直接暴力建边是 \(O(n^2)\) 的。
考虑直接把操作树建出来，即每次操作 W/Z x 就往 \(x\) 连一条 W 边或 Z 边，然后在这棵树上计算每个点被加入时，对其他点度数的贡献。（下面注意区分原图和操作树）（以下我们规定，画在左边的儿子比画在右边的儿子先加）
首先，如果只有两个点，这两个点以 W 边相连，那么互相产生 \(1\) 的贡献。
在此基础上，如果一直往上连 Z 边，那么原图构成一个完全二分图（即每对左部点和右部点都有连边），如图（W 边用实线表示，Z 边用虚线表示）（图 1）：
分成了两个连通块，每个点都对对面连通块的每个点产生 \(1\) 的贡献。以上讨论在 Subtask 2 中有充足的提示。
如果继续往下接，就会发现（图 2）：
如图，\(4,3\) 之间有贡献，\(2\cup 3,1\) 直接有贡献，但 \(4,1\) 之间没贡献。这里同样也要保证 \(4\) 和 \(3\) 之间的 W 边要比 \(4,3\) 中任意一条边先加。
我们总结一下产生贡献的形式，如下（图 3）：
必须保证两条边加入的时间 \(t1<t2\)。
这个结论证明不难，对路径长度归纳即可。
接下来考虑加入一个点时，怎么快速维护这些贡献。（图 4）
如上图，如果加入的是一条 W 边，那么只会对 红点 和 黑点 分别产生 \(1\) 的贡献，不会对蓝色区域的 Z 边连通块产生贡献，因为红边比这些边要后加。
如果加入的是 Z 边，那么有两种情况。
Part. 1
第一种情况如下图（图 5）：
黑边是 new 点一直往上走遇到的第一条 W 边，于是该点会和蓝色区域的 Z 边连通块互相产生贡献（蓝色虚线比黑色实线后加），但不会和橙色区域产生贡献（橙色虚线比黑色实线先加）。
为了维护这一贡献，我们对操作树进行重构，（图 6）
显然重构完还是一棵树，只不过把每个点按照加入 Z 边的时间，进行了拆点。
现在画出重构后的图 5：（图 6）
不难用树状数组维护。
Part. 2
第二种情况，（图 7）（左边是操作树，右边是重构树）
但接在绿色区域可能有很多连通块，不方便直接子树加，于是我们转换为绿色区域的链加-单点查，进而转换为单点加-子树查。同样不难用树状数组维护。
Code
为了方便处理，可以先遍历操作把重构树建出来，第二次遍历操作再进行贡献维护，也就是我们可以把已加入点对未加入点的贡献提前计算。
注意如果这样写的话，加入 W 边时也要对两个端点进行类似 Part. 1 和 Part. 2 的操作。
Code