维护一棵n个点的树, 初始权值为1, 支持: 路径权值加, 删除一条边并加入一条边 (保证操作完是一棵树), 路径权值乘, 询问路径点权和模51061的结果. (1≤n,q≤10^5, 0≤c≤10^4) 其实c的范围并不是这个. 爆int被坑了几次, 这次专门对每个式子计算了一番, 然后放心地提交, WA掉. 看了几个题解, 发现大家用unsigned, AC. 人与人起码的信任哪里去了......TAT 这是一道LCT模板题.
LCT用于维护树或森林, 支持加边, 删边, 换根, 路径修改, 路径查询. 一个经典应用是动态维护最小生成树.
和轻重链剖分一样, LCT把边划分为两类: 偏爱边, 非偏爱边. 一个点只能有一条出边是偏爱边, 偏爱边连成一条条偏爱路径. 一条偏爱路径用一棵辅助树 (Splay) 维护, 以深度为关键字. 每条偏爱路径有一个路径父亲 (Path Parent), 定义为深度最浅的点在原树中的父亲. 这样, 用一些平衡树和路径父亲就能完整地刻画一棵树 (虽然不支持子树操作).
LCT的核心操作是access. access(x)之后, 从根到x形成一条始于根, 终于x的偏爱路径. 这个过程中, 一些偏爱边失宠, 一些非偏爱边得宠. 现在, 这条路径的信息在一棵辅助树里, 问题简化为用Splay维护一个序列. 需要注意的是, access(x)之后, x不一定是辅助树的树根. 确切地说, 原来x到根的路径上有多少条非偏爱边, 现在x的深度就是多少 (从0开始标号).
access只能形成一条从根出发的偏爱路径. 为了操作任意路径, 需要支持换根. 方法是将根到x的路径上所有点的深度翻转 (最深<->最浅), 可通过翻转标记实现.
对无根树link(x, y), 需要将其中一个设为根, 再将它向另一个连一条非偏爱边.
一个点与许多边相邻, 为了指定cut哪条边, 需要另加一个参数. cut(x, y)表示删掉x靠近y的那条边. 方法是将y设为根, access(x), splay(x), 此时, 辅助树中, x只有左子树, 而连接左子树的这条边正是待删除的.
回答连通性可能需要寻找某点所在树的根, 方法是access(x), splay(x), 然后一直往左走, 直到左子树为空.
有根树中还可以求lca(x, y). 先access(x), 再access(y), 根到y的偏爱路径的辅助树的根即为所求.
以上是LCT的原理. 容易混淆的是两个概念: 原树和辅助树. 原来的一棵树用许许多多的辅助树来维护, 原树的根, 是access构造出的辅助树中最浅的一个点.
实现中, 将路径父亲记到辅助树的根上. 于是, 辅助树中, 如果一个结点不是根结点, 那么它的父亲和普通平衡树中的定义一样; 如果它是根结点, 那么它的父亲指针指向它的路径父亲, 但它既不是路径父亲在辅助树中的左儿子, 也不是右儿子 (实际上在两棵不同的辅助树树中).
判断一个结点是否是辅助树的根结点可以用一个isroot函数搞定, 类似地也可以判断某非根结点是左儿子还是右儿子. 但我的模板对每个点维护一个额外的t, 表示该点是根 (-1), 左儿子 (0), 还是右儿子 (1). 实测效率高了不少.
旋转的时候up一个点的信息即可, 因为另一个点还要继续转. 循环结束后, 再对被提到根的点up一下.
#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
using namespace std;
const int MOD = 51061, N = 1e5;
typedef long long ll;
typedef unsigned uint;
struct Node {
Node* ch[2], * fa;
uint a, b, v, sum, sz;
int t;
bool rev;
Node(uint=1, uint=1);
void operator+=(uint);
void operator*=(uint);
void setf(Node* f, int t1)
{
t = t1;
fa = f;
t >= 0 ? f->ch[t] = this : 0;
}
void reverse()
{
rev = !rev;
swap(ch[0], ch[1]);
ch[0]->t = 0;
ch[1]->t = 1;
}
void down()
{
if (rev) {
rev = false;
ch[0]->reverse();
ch[1]->reverse();
}
if (a != 1) {
*ch[0] *= a;
*ch[1] *= a;
a = 1;
}
if (b) {
*ch[0] += b;
*ch[1] += b;
b = 0;
}
}
void up()
{
(sum = ch[0]->sum + ch[1]->sum + v) %= MOD;
sz = ch[0]->sz + ch[1]->sz + 1;
}
} nodes[N+1], nil_node(0, 0), * nil = &nil_node;
Node::Node(uint v1, uint sz1): fa(nil), a(1), b(0), v(v1), sum(v1), sz(sz1), t(-1), rev(false)
{
ch[0] = ch[1] = nil;
}
inline void Node::operator+=(uint x)
{
if (this != nil) {
v += x; v -= v >= MOD ? MOD : 0;
b += x; b -= b >= MOD ? MOD : 0;
sum = (sum + (ll)x * sz) % MOD;
}
}
inline void Node::operator*=(uint x)
{
if (this != nil) {
(v *= x) %= MOD;
(a *= x) %= MOD;
(b *= x) %= MOD;
(sum *= x) %= MOD;
}
}
inline void rot(Node* y)
{
Node* x = y->fa;
int t = y->t;
y->setf(x->fa, x->t);
y->ch[t^1]->setf(x, t);
x->setf(y, t^1);
x->up();
}
void splay(Node* x)
{
static Node* S[N];
int top = 0;
Node* y;
for (y = x; y->t >= 0; y = y->fa) S[top++] = y;
for (y->down(); top; S[--top]->down()) ;
while (x->t >= 0) {
if ((y = x->fa)->t >= 0)
rot(x->t ^ y->t ? x : y);
rot(x);
}
x->up();
}
void access(Node* x)
{
for (Node* y = nil; x != nil; y = x, x = x->fa) {
splay(x);
x->ch[1]->t = -1;
y->setf(x, 1);
x->up();
}
}
inline void make_root(Node* x)
{
access(x);
splay(x);
x->reverse();
}
inline void link(Node* x, Node* y)
{
make_root(y);
y->setf(x, -1);
}
inline void cut(Node* x, Node* y)
{
make_root(y);
access(x);
splay(x);
x->ch[0]->setf(nil, -1);
x->ch[0] = nil;
x->up();
}
inline Node& path(Node* x, Node* y)
{
make_root(x);
access(y);
splay(y);
return *y;
}
int main()
{
int n, q;
scanf("%d%d", &n, &q);
Rep (i, 0, n-1) {
int u, v;
scanf("%d%d", &u, &v);
link(nodes + u, nodes + v);
}
while (q--) {
char op;
int u1, v1, u2, v2;
uint c;
scanf(" %c%d%d", &op, &u1, &v1);
Node* x = nodes + u1, * y = nodes + v1;
switch (op) {
case '+':
scanf("%u", &c);
path(x, y) += c;
break;
case '-':
scanf("%d%d", &u2, &v2);
cut(x, y);
link(nodes + u2, nodes + v2);
break;
case '*':
scanf("%u", &c);
path(x, y) *= c;
break;
default:
printf("%u\n", path(x, y).sum);
}
}
return 0;
}