[bzoj 2759] 一个动态树好题

n个未知数和n个等式组成的同余方程组: x[i] = k[i] x[p[i]] + b[i] mod 10007 (1≤i≤n), k[i], b[i], x[i] 是[0,10007)内的整数. q个操作: - 询问当前x[a]的解, 无解输出-1, 多解输出-2. - 修改一个等式, 形式依然是 x[i] = k[i] x[p[i]] + b[i] mod 10007.

(1≤n≤3*10^4, 0≤q≤10^5, 时限2秒, 询问事务约占80%) 本题的名称即为 <一个动态树好题>, 也的确是好题. 既然作者说这是一个动态树好题, 就来找找同余方程和动态树的联系.

每一条方程可以用一个二元组(k,b)描述, 不妨看成一次函数 (课本上说k不能等于0, 本文忽略这一限制). 一次函数之间的复合是容易的, 并且函数的复合运算满足结合律. 单位元是(1,0).

对于每一条方程, 将p[i]向i连一条有向边, 则每个结点有且只有一个父亲, 形成一片有向基环森林. 每棵有向基环树中变量的情况都是能确定下来的. 有向基环树与有根树的唯一区别是多了一条由根指向后代的边. 不妨把它砍掉, 然后用LCT维护. 砍掉之前, 将这条方程与原来的等式推导出的方程联立, 解出根结点对应的值, 并保存下来. 这样信息就不会丢失了. 只要支持查询根结点到每个点的函数关系, 再把先前保存的值代入, 就能回答询问. 本段所有 "根结点" 指的是有向树的树根, 不是Splay的树根.

LCT支持链查询的方法是, 通过access+splay操作, 将某点到根的路径装进一棵Splay树, 查询这棵Splay树的信息. 即, 把链的查询转化为子树查询. 对于每个点, 设原本的函数为f, 所在Splay子树的所有f按中序遍历的顺序复合得到g, 维护f,g. 其中f仅在修改操作改变, 空结点和根结点的f=(1,0). 现在, access+splay, g即是根结点到某点的函数关系.

初始化的时候需要link, 修改不妨看成cut和link两个步骤.

设link(x,y,f)添加一个函数: f(x)=y. 若x, y不在同一棵树中, 直接将y的设置为x的非偏爱儿子. 否则, 解出y的值并保存下来, 不对树的形态做改变. 逆元可以预处理.

设cut(x,y)删除原来的函数f(x)=y, 设x, y所在树的树根为r, 被砍掉的r的父亲为p. 如果y=r, 不用改动树的形态. 若y在原有向基环树的环上, 砍掉(x,y), 连上(p,r), 因为原来的解失效了, 但函数关系仍然在; 否则, 只砍掉(x,y). 判断是否在环上的一个方法是看y是否为p或p的祖先, 求lca(p,y)即可. 有根树求lca, 两次access就好. 无论是哪种情况, y都成了树根, 不要忘记先前对树根的约定: f=(1,0), 保存根结点的解 (现在一定变成了多解).

其他题解的方法和我的相似, 不过上述做法常数较小, 不加读入优化bzoj上rank 14, 加了是rank 1.

线性求逆元的方法给个推导:

要求p是素数, 以确保[1,p)逆元存在.

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
 
using namespace std;
const int MOD = 10007, N = 30000;
int inv[MOD];
 
struct Fun {
    int k, b;
    Fun(int k=1, int b=0): k(k), b(b) {}
    Fun operator*(const Fun& o) const
    {
        return Fun(k * o.k % MOD, (o.k * b + o.b) % MOD);
    }
    int operator()(const int x) const
    {
        return x < 0 ? x : (k*x + b) % MOD;
    }
};
 
struct Equation {
    int p;
    Fun f;
} E[N + 1];
 
struct Node {
    Node* ch[2], * fa;
    int t, x;
    Fun f, g;
    Node();
    void setf(Node* f1, int t1)
    {
        fa = f1;
        t = t1;
        t >= 0 ? fa->ch[t] = this : 0;
    }
    void up()
    {
        g = ch[0]->g * f * ch[1]->g;
    }
} nodes[N + 1], * nil = nodes;
 
Node::Node(): fa(0), t(-1), x(-2) { ch[0] = ch[1] = nil; }
 
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)
{
    Node* y;
    while (x->t >= 0) {
        if ((y = x->fa)->t >= 0)
            rot(x->t ^ y->t ? x : y);
        rot(x);
    }
    x->up();
}
 
Node* access(Node* x)
{
    Node* y;
    for (y = nil; x; y = x, x = x->fa) {
        splay(x);
        x->ch[1]->t = -1;
        y->setf(x, 1);
        x->up();
    }
    return y;
}
 
Node* get_root(Node* x)
{
    access(x);
    splay(x);
    while (x->ch[0] != nil) x = x->ch[0];
    return x;
}
 
Fun get_fun(Node* x)
{
    access(x);
    splay(x);
    return x->g;
}
 
// f: x -> y
// y is the root of a tree
inline void link(Node* x, Node* y, const Fun& f)
{
    Node* rx = get_root(x), * ry = get_root(y);
    if (rx == ry) {
        Fun yy = get_fun(x) * f;
        if (yy.k == 1)
            y->x = yy.b ? -1 : -2;
        else
            y->x = yy.b * inv[(1 + MOD - yy.k) % MOD] % MOD;
    } else {
        y->f = f;
        y->up();
        y->setf(x, -1);
    }
}
 
// x->y
inline void cut(Node* x, Node* y)
{
    Node* r = get_root(y), * p, * z;
    const Equation& e = E[r - nodes];
    y->x = -2;
    if (r == y) return;
    access(p = nodes + e.p);
    z = access(y);
    splay(y);
    y->ch[0]->setf(0, -1);
    y->ch[0] = nil;
    y->f = Fun();
    y->up();
    if (z == y) link(p, r, e.f);
}
 
void init()
{
    inv[1] = 1;
    Rep (i, 2, MOD)
        inv[i] = (MOD - MOD/i) * inv[MOD % i] % MOD;
}
 
int main()
{
    init();
    int n;
    scanf("%d", &n);
    For (i, 1, n) {
        scanf("%d%d%d", &E[i].f.k, &E[i].p, &E[i].f.b);
        link(nodes + E[i].p, nodes + i, E[i].f);
    }
    int q;
    scanf("%d", &q);
    while (q--) {
        char op;
        int a, k, p, b;
        scanf(" %c%d", &op, &a);
        if (op == 'A') {
            Node* r = get_root(nodes + a);
            printf("%d\n", nodes[a].g(r->x));
        } else {
            scanf("%d%d%d", &k, &p, &b);
            cut(nodes + E[a].p, nodes + a);
            E[a] = (Equation){p, Fun(k, b)};
            link(nodes + p, nodes + a, E[a].f);
        }
    }
    return 0;
}