题目链接
https://www.lydsy.com/JudgeOnline/problem.php?id=2959
题解
真是被这题搞得心态大崩……调了7个小时……然而并查集都能写成(O(n^2))的我还能怪谁呢
显然要把每个边双连通分量缩成点，点权为边双连通分量内所有点点权和，然后答案就等于两点路径上点权和
现在需要用LCT维护，就比较麻烦
大概是一边LCT一边使用并查集分别维护连通块和边双连通分量
加边时，若两点不联通，则link, 然后在维护连通块的并查集里并起来
若两点联通但不在同一边双中，则把这两个点路径上的所有边双缩到一起（其实就是“删除点”），顺便加入到边双连通分量的并查集中
这个可以通过把路径的splay提取出来进行DFS实现，因为每个点只会被删一次所以复杂度正确
但是这里由于缩点，我们每次在lct中访问父亲的时候要求它树上父亲在并查集里的代表元素。。。所以很容易写错
时间复杂度(O(nlog nalpha(n))).
代码
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cassert>
#include<ctime>
#define llong long long
using namespace std;
const int N = 1.5e5;
struct SplayNode
{
int son[2],fa,sum,val,rev;
} spl[N+3];
int uf1[N+3],uf2[N+3];
int stk[N+3];
int a[N+3];
int n,q;
inline int read()
{
int ret = 0; char ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
while(ch >= '0' && ch <= '9') ret = (ret << 3) + (ret << 1) + ch - '0' , ch = getchar();
return ret;
}
int findfa(int id,int u)
{
if(id==0)
{
int i = u;
while(u!=uf1[u]) {u = uf1[u];}
while(uf1[i]!=u)
{
int j = uf1[i]; uf1[i] = u; i = j;
}
}
else
{
int i = u;
while(u!=uf2[u]) {u = uf2[u];}
while(uf2[i]!=u)
{
int j = uf2[i]; uf2[i] = u; i = j;
}
}
return u;
}
bool isroot(int u) {int uu = findfa(1,spl[u].fa); return spl[uu].son[0]!=u && spl[uu].son[1]!=u;}
bool sondir(int u) {return u==spl[findfa(1,spl[u].fa)].son[1];}
void pushup(int u)
{
spl[u].sum = spl[spl[u].son[0]].sum+spl[u].val+spl[spl[u].son[1]].sum;
}
void pushdown(int u)
{
int ls = spl[u].son[0],rs = spl[u].son[1];
if(spl[u].rev)
{
spl[u].rev = 0;
if(ls)
{
swap(spl[ls].son[0],spl[ls].son[1]);
spl[ls].rev ^= 1;
}
if(rs)
{
swap(spl[rs].son[0],spl[rs].son[1]);
spl[rs].rev ^= 1;
}
}
}
void rotate(int u)
{
int x = findfa(1,spl[u].fa),y = findfa(1,spl[x].fa); bool dir = sondir(u)^1;
if(!isroot(x)) {spl[y].son[sondir(x)] = u;}
spl[u].fa = y;
spl[x].son[dir^1] = spl[u].son[dir];
if(spl[x].son[dir^1]) {spl[spl[x].son[dir^1]].fa = x;}
spl[u].son[dir] = x; spl[x].fa = u;
pushup(x);
}
void splaynode(int u)
{
int x = u,tp = 0,y;
while(!isroot(x)) {tp++; stk[tp] = x; x = findfa(1,spl[x].fa);}
pushdown(x);
while(tp) {pushdown(stk[tp]); tp--;}
while(!isroot(u))
{
x = findfa(1,spl[u].fa),y = findfa(1,spl[x].fa);
if(!isroot(x)) {sondir(x)^sondir(u) ? rotate(u) : rotate(x);}
rotate(u);
}
pushup(u);
}
void access(int u)
{
for(int i=0; u; i=u,u=findfa(1,spl[u].fa))
{
splaynode(u);
spl[u].son[1] = i; pushup(u);
}
}
void makeroot(int u)
{
access(u); splaynode(u);
spl[u].rev ^= 1; swap(spl[u].son[0],spl[u].son[1]);
}
void link(int u,int v)
{
makeroot(u); spl[u].fa = v;
}
void dfs(int u,int u0)
{
uf2[u] = u0;
pushdown(u);
if(spl[u].son[0]) dfs(spl[u].son[0],u0);
if(spl[u].son[1]) dfs(spl[u].son[1],u0);
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1; i<=n; i++) uf1[i] = uf2[i] = i;
for(int i=1; i<=n; i++) a[i] = read(),spl[i].val = spl[i].sum = a[i];
while(q--)
{
int opt; opt = read();
if(opt==1)
{
int u,v; u = read(),v = read();
int uu = findfa(0,u),vv = findfa(0,v);
if(uu!=vv)
{
link(findfa(1,u),findfa(1,v));
uf1[uu] = vv;
}
else
{
uu = findfa(1,u),vv = findfa(1,v);
makeroot(uu); access(vv); splaynode(vv);
spl[vv].val = spl[vv].sum;
dfs(vv,vv);
spl[vv].son[0] = 0;
}
}
else if(opt==2)
{
int u,x; u = read(),x = read(); int delta = x-a[u]; a[u] = x;
int uu = findfa(1,u); splaynode(uu);
spl[uu].val += delta; spl[uu].sum += delta;
}
else if(opt==3)
{
int u,v; u = read(),v = read();
int uu = findfa(1,u),vv = findfa(1,v);
int uuu = findfa(0,uu),vvv = findfa(0,vv);
if(uuu!=vvv) {puts("-1"); continue;}
else
{
makeroot(uu); access(vv); splaynode(vv);
printf("%d
",spl[vv].sum);
}
}
}
return 0;
}