题解：P5220 特工的信息流

· · 题解

后缀积和还是太难了，会用矩乘就把脑子丢掉了。

考虑这个走路径的过程在干嘛，不难发现如果我们设初始值为 0，那么按照路径顺序，走过一个权值为 a 点，等价于对当前的值做一次 f(x)=ax+a 的函数变换。由于这是一个一次函数，所以我们考虑构造矩阵。

\begin{bmatrix} ax+a \\ 1 \end{bmatrix} = \begin{bmatrix} a & a \\ 0 & 1 \end{bmatrix} \begin{bmatrix} x \\ 1 \end{bmatrix}

不难注意到上述等式可以维护我们的答案，于是我们直接用树剖与线段树维护即可。

#include <bits/stdc++.h>
#define N 100010
#define mod 20924
#define M N << 2
#define ls nw << 1
#define rs nw << 1 | 1
using namespace std;
int n, m;
int a[N];
vector<int> nxt[N];
struct Mat { int m[2][2]; };
inline Mat operator*(const Mat& a, const Mat& b)
{
    Mat c;
    c.m[0][0] = (a.m[0][0] * b.m[0][0] + a.m[0][1] * b.m[1][0]) % mod;
    c.m[0][1] = (a.m[0][0] * b.m[0][1] + a.m[0][1] * b.m[1][1]) % mod;
    c.m[1][0] = (a.m[1][0] * b.m[0][0] + a.m[1][1] * b.m[1][0]) % mod;
    c.m[1][1] = (a.m[1][0] * b.m[0][1] + a.m[1][1] * b.m[1][1]) % mod;
    return c;
}
inline Mat gt(const int& v)
{
    Mat res;
    res.m[0][0] = v, res.m[0][1] = v;
    res.m[1][0] = 0, res.m[1][1] = 1;
    return res;
}
int dep[N], fa[N], top[N], siz[N], son[N], dfn[N], dfc, dfh[N];
void dfs1(const int& u, const int& f)
{
    dep[u] = dep[f] + 1, fa[u] = f, siz[u] = 1;
    for (const int& v : nxt[u])
        if (v != f)
            dfs1(v, u), siz[u] += siz[v];
    if (f && siz[u] > siz[son[f]]) son[f] = u;
}
void dfs2(const int& u, const int& r)
{
    top[u] = r, dfn[u] = ++dfc, dfh[dfc] = u;
    if (!son[u]) return;
    dfs2(son[u], r);
    for (const int& v : nxt[u])
        if (v != fa[u] && v != son[u])
            dfs2(v, v);
}
pair<Mat, Mat> seg[M];
inline pair<Mat, Mat> merg(const pair<Mat, Mat>& a, const pair<Mat, Mat>& b) { return { a.first * b.first,b.second * a.second }; }
void build(const int& nw, const int& l, const int& r)
{
    if (l == r) return (void)(seg[nw].first = seg[nw].second = gt(a[dfh[l]]));
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    seg[nw] = merg(seg[ls], seg[rs]);
}
inline void modify(const int& nw, const int& l, const int& r, const int& p, const int& v)
{
    if (l == r) return (void)(seg[nw].first = seg[nw].second = gt(a[dfh[l]] = (a[dfh[l]] + v) % mod));
    int mid = (l + r) >> 1;
    if (p <= mid) modify(ls, l, mid, p, v);
    else modify(rs, mid + 1, r, p, v);
    seg[nw] = merg(seg[ls], seg[rs]);
}
inline pair<Mat, Mat> query(const int& nw, const int& l, const int& r, const int& pl, const int& pr)
{
    if (pl <= l && r <= pr) return seg[nw];
    int mid = (l + r) >> 1;
    if (pl <= mid && mid < pr) return merg(query(ls, l, mid, pl, pr), query(rs, mid + 1, r, pl, pr));
    if (pl <= mid) return query(ls, l, mid, pl, pr);
    else return query(rs, mid + 1, r, pl, pr);
}
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    static int u, v;
    for (int i = 1; i < n; i++) cin >> u >> v, nxt[u].push_back(v), nxt[v].push_back(u);
    dfs1(1, 0); dfs2(1, 1);
    build(1, 1, n);
    static char op;
    while (m--)
    {
        cin >> op >> u >> v;
        if (op == 'C') modify(1, 1, n, dfn[u], v);
        else
        {
            Mat res1, res2;
            res1.m[0][0] = res2.m[0][0] = res1.m[1][1] = res2.m[1][1] = 1;
            res1.m[0][1] = res2.m[0][1] = res1.m[1][0] = res2.m[1][0] = 0;
            while (top[u] != top[v])
            {
                if (dep[top[u]] > dep[top[v]]) res1 = query(1, 1, n, dfn[top[u]], dfn[u]).first * res1, u = fa[top[u]];
                else res2 = res2 * query(1, 1, n, dfn[top[v]], dfn[v]).second, v = fa[top[v]];
            }
            if (dep[u] > dep[v]) res1 = query(1, 1, n, dfn[v], dfn[u]).first * res1;
            else res2 = res2 * query(1, 1, n, dfn[u], dfn[v]).second;
            cout << (res2 * res1).m[0][1] << '\n';
        }
    }
    return 0;
}