n 个节点的无向图, 支持三类共 m 个操作: - 连接 A,B - 修改 A 的点权为 B - 给边任意定向, 从 A 走到 B, 边和点的经过次数不限, 求所到点点权之和的最大值; 或报告 A,B 不连通
(m ≤ 5n, 每个点的点权始终不超过 10^4, n ≤ 1.5*10^5) 把边-双连通分量缩成点, 一般图就变成了树. 显然, 不在树上 A,B 间路径上的点无法到达. 猜测从边-双连通分量的某个点出发, 可以遍历整个双连通分量, 并且从指定点离开. 那么, 只要支持快速地动态缩点, 我们可以用 LCT 维护: 一条边连接同一连通块中的两点, 把路径上的所有点缩起来.
原先想用启发式合并. 直接用并查集缩点, 也许会产生一个点伸出不止两条重边的情况......然而, 实际上并不会. 通过make_root+access, 需要被缩起来的点好好地呆在了一棵 Splay 里, 它们和外部只有轻边相连. 把 Splay DFS 一遍, 用并查集把所有点合并, 用并查集的根 r 所在的点代表这个边双. r 的权值即整个边双的权值, 它的左右儿子置为空. 那么, 在可能访问轻边的时候用并查集重定向一下, 其他照常处理就好. 因为重边都是后来连上的.
reverse那里要写成t[ch[x][0]] = 0, t[ch[x][1]] = 1; 不能写swap(t[ch[x][0]], t[ch[x][1]]); 因为空节点的 t 是未定义的.
const int N = 1.5e5 + 1;
struct UF
{
int f[N], rk[N];
int F(int x)
{
return f[x] ? f[x] = F(f[x]) : x;
}
void merge(int x, int y)
{
x = F(x), y = F(y);
assert(x != y);
if (rk[x] < rk[y]) swap(x, y);
f[y] = x;
rk[x] += rk[x] == rk[y];
}
} U, C;
struct LCT
{
int ptr, ch[N][2], fa[N], t[N], sum[N], val[N];
bool rev[N];
LCT()
{
memset(t, -1, sizeof t);
}
void setc(int x, int d, int y)
{
if (x && d != -1) ch[x][d] = y;
fa[y] = x, t[y] = d;
}
void up(int x)
{
sum[x] = sum[ch[x][0]] + val[x] + sum[ch[x][1]];
}
void reverse(int x)
{
rev[x] ^= 1;
swap(ch[x][0], ch[x][1]);
t[ch[x][0]] = 0, t[ch[x][1]] = 1;
}
void down(int x)
{
if (rev[x])
{
reverse(ch[x][0]), reverse(ch[x][1]);
rev[x] = 0;
}
}
void rot(int x)
{
int d = t[x], y = fa[x];
setc(U.F(fa[y]), t[y], x);
setc(y, d, ch[x][d^1]);
setc(x, d^1, y);
up(y);
}
void splay(int x)
{
static int S[N];
int y, top = 0;
for (y = x; t[y] != -1; y = fa[y]) S[top++] = y;
for (down(y); top; down(S[--top])) ;
while (t[x] != -1)
{
if (t[y = fa[x]] != -1) rot(t[x] ^ t[y] ? x : y);
rot(x);
}
up(x);
}
void access(int x)
{
for (int y = 0; x; y = x, x = U.F(fa[x]))
{
splay(x);
t[ch[x][1]] = -1;
setc(x, 1, y);
up(x);
}
}
void make_root(int x)
{
access(x);
splay(x);
reverse(x);
}
void link(int x, int y)
{
x = U.F(x), y = U.F(y);
if (x == y) return;
make_root(x);
if (C.F(x) == C.F(y))
{
access(y);
splay(y);
int tmp = sum[y];
shrink(y);
y = U.F(y);
fa[y] = ch[y][0] = ch[y][1] = 0;
t[y] = -1;
sum[y] = val[y] = tmp;
}
else
{
setc(y, -1, x);
C.merge(x, y);
}
}
void shrink(int x)
{
if (ch[x][0]) U.merge(ch[x][0], x), shrink(ch[x][0]);
if (ch[x][1]) U.merge(ch[x][1], x), shrink(ch[x][1]);
}
void add(int x, int v)
{
x = U.F(x);
splay(x);
val[x] += v;
sum[x] += v;
}
int query(int x, int y)
{
x = U.F(x), y = U.F(y);
if (C.F(x) != C.F(y)) return -1;
make_root(x);
access(y);
splay(y);
return sum[y];
}
} T;
int v[N];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
rep (i, 1, n+1) scanf("%d", v+i), T.sum[i] = T.val[i] = v[i];
while (m--)
{
int p, a, b;
scanf("%d%d%d", &p, &a, &b);
if (p == 1) T.link(a, b);
else if (p == 2) T.add(a, b-v[a]), v[a] = b;
else printf("%d\n", T.query(a, b));
}
return 0;
}