题面戳我

题解 litble 说的很好了：https://blog.csdn.net/litble/article/details/87908682

截个屏转发一下_(:зゝ∠)_

---

---

以及 immortalco 的博客（懒得截图了）：http://immortalco.blog.uoj.ac/blog/2625

此题大部分同学都写了 $\log _ 2 ^ 2$的树链剖分，复杂度大概是 $m \times \log _ 2 ^ 2 n \times 128 \times 4$（其实最后那个常数甚至不止 $4$），这个值约为 $3.4 \times 10 ^ 9$，是不可能通过此题的。

然而原版数据很水，让 $\log _ 2 ^ 2$过了，原因就是流传甚广的 “树剖跑不满”

于是写了 $\log _ 2 ^ 2$且常数最大的 boshi 同学为我们造了一组可以把树剖卡满 $\log _ 2 ^ 2$的数据：

下载链接

原理也非常简单：构造的树包含 $\log$条重链就行了

这份数据也已经上传到了洛谷上，感谢 LK 的支持

这样一般树剖是跑不过去的，那么有以下两种方法：

• 使用 avx 指令集暴力卡常数
• 使用全局平衡二叉树（其实就是静态 lct）去掉一个 $\log$

我选择了后者

代码：

#include <bits/stdc++.h>

#define NS (30005)
#define MS (128)
#define MOD (10007)

using namespace std;

inline short pls(short a, short b) { return a + b < MOD ? a + b : a + b - MOD; }
inline short mns(short a, short b) { return a - b < 0 ? a - b + MOD : a - b; }
inline short mul(short a, short b) { return (int)a * b % MOD; }

template<typename _Tp> inline void IN(_Tp &dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, Q;

short m, V[NS], inv[MOD];

struct graph
{
    int head[NS], nxt[NS << 1], to[NS << 1], sz;
    graph() { memset(head, -1, sizeof(head)), sz = 0; }
    inline void push(int a, int b)
    {
        nxt[sz] = head[a], to[sz] = b, head[a] = sz++;
    }
    inline int operator [] (const int a) const { return to[a]; }
} g;

struct poly
{
    short d[MS];
    inline short &operator [] (const short a) { return d[a]; }
    void fwt(bool t)
    {
        for (short l = 1; l < m; l <<= 1)
            for (short i = 0; i < m; i += (l << 1))
                for (short j = i, t1, t2; j < i + l; j += 1)
                {
                    t1 = d[j], t2 = d[j + l];
                    d[j] = pls(t1, t2), d[j + l] = mns(t1, t2);
                }
        if (!t) for (short i = 0; i < m; i += 1) d[i] = mul(d[i], inv[m]);
    }
    inline poly operator + (poly oth) const
    {
        static poly res;
        for (short i = 0; i < m; i += 1) res[i] = pls(d[i], oth[i]);
        return res;
    }
    inline poly operator - (poly oth) const
    {
        static poly res;
        for (short i = 0; i < m; i += 1) res[i] = mns(d[i], oth[i]);
        return res;
    }
    inline poly operator * (poly oth) const
    {
        static poly res;
        for (short i = 0; i < m; i += 1) res[i] = mul(d[i], oth[i]);
        return res;
    }
} one[MS];

struct matrix
{
    poly a, b, c, d;
    inline void operator *= (matrix oth)
    {
        static matrix tmp;
        tmp.a = a * oth.a;
        tmp.b = b + a * oth.b;
        tmp.c = oth.a * c + oth.c;
        tmp.d = oth.b * c + d + oth.d;
        a = tmp.a, b = tmp.b, c = tmp.c, d = tmp.d;
    }
};

int sz[NS], hs[NS], root, A[NS];

struct N
{
    int s[2], fa;
    short zero[MS];
    poly lf, lh;
    matrix m;
    inline poly &f() { return m.c; }
    inline poly &h() { return m.d; }
} e[NS];

bool isrt(int a) { return e[e[a].fa].s[0] != a && e[e[a].fa].s[1] != a; }

void preWork()
{
    short tmp = m;
    m = 1;
    while (m < tmp) m <<= 1;
    inv[1] = 1;
    for (short i = 2; i < MOD; i += 1)
        inv[i] = mul(mns(0, MOD / i), inv[MOD % i]);
    for (short i = 0; i < m; i += 1) one[i][i] = 1, one[i].fwt(1);
    for (int i = 1; i <= n; i += 1) e[i].lf = one[0];
}

void dfs(int a, int fa)
{
    sz[a] = 1;
    for (int i = g.head[a]; ~i; i = g.nxt[i])
        if (g[i] != fa)
        {
            dfs(g[i], a), sz[a] += sz[g[i]];
            if (sz[g[i]] > sz[hs[a]]) hs[a] = g[i];
        }
}

void pup(int a)
{
    int l = e[a].s[0], r = e[a].s[1];
    static matrix x;
    x.a = one[V[a]];
    for (short i = 0; i < m; i += 1)
        if (e[a].zero[i]) x.a[i] = 0;
        else x.a[i] = mul(x.a[i], e[a].lf[i]);
    x.b = x.c = x.a;
    for (short i = 0; i < m; i += 1) x.d[i] = pls(x.a[i], e[a].lh[i]);
    if (r) e[a].m = e[r].m, e[a].m *= x;
    else e[a].m = x;
    if (l) e[a].m *= e[l].m;
}

void pupl(int a, int b, bool t)
{
    static poly tmp;
    tmp = e[b].f() + one[0];
    if (t)
    {
        e[a].lh = e[a].lh + e[b].h();
        for (short i = 0; i < m; i += 1)
            if (!tmp[i]) e[a].zero[i]++;
            else e[a].lf[i] = mul(e[a].lf[i], tmp[i]);
    }
    else
    {
        e[a].lh = e[a].lh - e[b].h();
        for (short i = 0; i < m; i += 1)
            if (!tmp[i]) e[a].zero[i]--;
            else e[a].lf[i] = mul(e[a].lf[i], inv[tmp[i]]);
    }
}

int build(int l, int r)
{
    if (l > r) return 0;
    int sum = 0, tot = sz[A[l]], mid = l;
    for (int i = l; i <= r; i += 1) sum += sz[A[i]];
    while ((tot << 1) <= sum) mid++, tot += sz[A[mid]];
    int a = A[mid];
    e[a].s[0] = build(l, mid - 1), e[a].s[1] = build(mid + 1, r);
    if (e[a].s[0]) e[e[a].s[0]].fa = a;
    if (e[a].s[1]) e[e[a].s[1]].fa = a;
    pup(a);
    return a;
}

bool book[NS];

int construct(int a)
{
    for (int i = a; i; i = hs[i]) book[i] = 1;
    for (int i = a; i; i = hs[i])
        for (int j = g.head[i]; ~j; j = g.nxt[j])
            if (!book[g[j]])
            {
                int k = construct(g[j]);
                e[k].fa = i, pupl(i, k, 1);
            }
    A[0] = 0;
    for (int i = a; i; i = hs[i]) A[++A[0]] = i;
    for (int i = 1; i < A[0]; i += 1) sz[A[i]] -= sz[A[i + 1]];
    return build(1, A[0]);
}

void modify(int a, short d)
{
    V[a] = d;
    while (a)
    {
        if (e[a].fa && isrt(a))
            pupl(e[a].fa, a, 0), pup(a), pupl(e[a].fa, a, 1);
        else pup(a);
        a = e[a].fa;
    }
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), preWork();
    for (int i = 1; i <= n; i += 1) IN(V[i]);
    for (int i = 1, a, b; i < n; i += 1)
        IN(a), IN(b), g.push(a, b), g.push(b, a);
    dfs(1, 0), root = construct(1), IN(Q);
    static char opt[10];
    int a; short b;
    while (Q--)
    {
        scanf("%s", opt), IN(a);
        if (opt[0] == 'C') IN(b), modify(a, b);
        else
        {
            e[root].h().fwt(0);
            printf("%d\n", e[root].h()[a]);
            e[root].h().fwt(1);
        }
    }
    return 0;
}

卡常版：

#include <bits/stdc++.h>

#define NS (30005)
#define MS (128)
#define MOD (10007)

using namespace std;

inline int pls(int a, int b) { return a + b < MOD ? a + b : a + b - MOD; }
inline int mns(int a, int b) { return a - b < 0 ? a - b + MOD : a - b; }
inline int mul(int a, int b) { return a * b % MOD; }

inline char getC()
{
    static char buf[2000000], *p = buf, *q = buf;
    if (p == q)
    {
        q = (p = buf) + fread(buf, 1, 2000000, stdin);
        if (p == q) return EOF;
    }
    return *p++;
}

template<typename _Tp> inline void IN(_Tp &dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getC(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getC();
    if (flag) dig = -dig;
}

void getS(char *a)
{
    static char c;
    while (c = getC(), !isalpha(c));
    while (isalpha(c)) *a = c, a++, c = getC();
}

int n, Q;

int m, V[NS], inv[MOD];

struct graph
{
    int head[NS], nxt[NS << 1], to[NS << 1], sz;
    graph() { memset(head, -1, sizeof(head)), sz = 0; }
    inline void push(int a, int b)
    {
        nxt[sz] = head[a], to[sz] = b, head[a] = sz++;
    }
    inline int operator [] (const int a) const { return to[a]; }
} g;

struct poly
{
    int d[MS];
    inline int &operator [] (const int a) { return d[a]; }
    void fwt(bool t)
    {
        for (int l = 1; l < m; l <<= 1)
            for (int i = 0; i < m; i += (l << 1))
                for (int j = i, t1, t2; j < i + l; j += 1)
                {
                    t1 = d[j], t2 = d[j + l];
                    d[j] = pls(t1, t2), d[j + l] = mns(t1, t2);
                }
        if (!t) for (int i = 0; i < m; i += 1) d[i] = mul(d[i], inv[m]);
    }
} one[MS];

struct matrix
{
    poly a, b, c, d;
    inline void operator *= (matrix &oth)
    {
        static int ta, tb, tc, td;
        for (int i = 0; i < m; i += 1)
        {
            ta = mul(a[i], oth.a[i]);
            tb = pls(b[i], mul(a[i], oth.b[i]));
            tc = pls(mul(oth.a[i], c[i]), oth.c[i]);
            td = pls(mul(oth.b[i], c[i]), pls(d[i], oth.d[i]));
            a[i] = ta, b[i] = tb, c[i] = tc, d[i] = td;
        }
    }
};

int sz[NS], hs[NS], root, A[NS];

struct N
{
    int s[2], fa;
    short zero[MS];
    poly lf, lh;
    matrix m;
    inline poly &f() { return m.c; }
    inline poly &h() { return m.d; }
} e[NS];

bool isrt(int a) { return e[e[a].fa].s[0] != a && e[e[a].fa].s[1] != a; }

void preWork()
{
    int tmp = m;
    m = 1;
    while (m < tmp) m <<= 1;
    inv[1] = 1;
    for (int i = 2; i < MOD; i += 1)
        inv[i] = mul(mns(0, MOD / i), inv[MOD % i]);
    for (int i = 0; i < m; i += 1) one[i][i] = 1, one[i].fwt(1);
    for (int i = 1; i <= n; i += 1) e[i].lf = one[0];
}

void dfs(int a, int fa)
{
    sz[a] = 1;
    for (int i = g.head[a]; ~i; i = g.nxt[i])
        if (g[i] != fa)
        {
            dfs(g[i], a), sz[a] += sz[g[i]];
            if (sz[g[i]] > sz[hs[a]]) hs[a] = g[i];
        }
}

void pup(int a)
{
    int l = e[a].s[0], r = e[a].s[1];
    static matrix x;
    x.a = one[V[a]];
    for (int i = 0; i < m; i += 1)
    {
        if (e[a].zero[i]) x.a[i] = 0;
        else x.a[i] = mul(x.a[i], e[a].lf[i]);
        x.d[i] = pls(x.a[i], e[a].lh[i]);
    }
    x.b = x.c = x.a;
    if (r) e[a].m = e[r].m, e[a].m *= x;
    else e[a].m = x;
    if (l) e[a].m *= e[l].m;
}

void pupl(int a, int b, bool t)
{
    if (t)
        for (int i = 0, tmp; i < m; i += 1)
        {
            e[a].lh[i] = pls(e[a].lh[i], e[b].h()[i]);
            tmp = pls(e[b].f()[i], 1);
            if (!tmp) e[a].zero[i]++;
            else e[a].lf[i] = mul(e[a].lf[i], tmp);
        }
    else
        for (int i = 0, tmp; i < m; i += 1)
        {
            e[a].lh[i] = mns(e[a].lh[i], e[b].h()[i]);
            tmp = pls(e[b].f()[i], 1);
            if (!tmp) e[a].zero[i]--;
            else e[a].lf[i] = mul(e[a].lf[i], inv[tmp]);
        }
}

int build(int l, int r)
{
    if (l > r) return 0;
    int sum = 0, tot = sz[A[l]], mid = l;
    for (int i = l; i <= r; i += 1) sum += sz[A[i]];
    while ((tot << 1) <= sum) mid++, tot += sz[A[mid]];
    int a = A[mid];
    e[a].s[0] = build(l, mid - 1), e[a].s[1] = build(mid + 1, r);
    if (e[a].s[0]) e[e[a].s[0]].fa = a;
    if (e[a].s[1]) e[e[a].s[1]].fa = a;
    pup(a);
    return a;
}

bool book[NS];

int construct(int a)
{
    for (int i = a; i; i = hs[i]) book[i] = 1;
    for (int i = a; i; i = hs[i])
        for (int j = g.head[i]; ~j; j = g.nxt[j])
            if (!book[g[j]])
            {
                int k = construct(g[j]);
                e[k].fa = i, pupl(i, k, 1);
            }
    A[0] = 0;
    for (int i = a; i; i = hs[i]) A[++A[0]] = i;
    for (int i = 1; i < A[0]; i += 1) sz[A[i]] -= sz[A[i + 1]];
    return build(1, A[0]);
}

void modify(int a, int d)
{
    V[a] = d;
    while (a)
    {
        if (e[a].fa && isrt(a))
            pupl(e[a].fa, a, 0), pup(a), pupl(e[a].fa, a, 1);
        else pup(a);
        a = e[a].fa;
    }
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), preWork();
    for (int i = 1; i <= n; i += 1) IN(V[i]);
    for (int i = 1, a, b; i < n; i += 1)
        IN(a), IN(b), g.push(a, b), g.push(b, a);
    dfs(1, 0), root = construct(1), IN(Q);
    static char opt[10];
    int a; int b;
    while (Q--)
    {
        getS(opt), IN(a);
        if (opt[0] == 'C') IN(b), modify(a, b);
        else
        {
            e[root].h().fwt(0);
            printf("%d\n", e[root].h()[a]);
            e[root].h().fwt(1);
        }
    }
    return 0;
}

后记

搞这个卡链剖弄得十分不愉快，比如被 litble 骂了，还弄的 litble 很不爽

但是我认为这个行为并不毒瘤，理由如下：

• 我并没有卡常，题目时空限制是出题人给的
• 我没有违规，所有数据均符合题面给出的范围
• 为什么卡树剖=毒瘤？谁写树剖的时候复杂度不是按两个 $\log$算的？我卡也没把你卡成 $\sqrt n$啊。既然知道 SPFA 可以被卡而不敢打，那树剖可以被卡怎么还会认为它没问题呢？
• 我也并不是恶意想让除我以外的人都过不了，我只是想让大家知道这题 $\log _ 2 ^ 2$的链剖复杂度是错误的，$3.4 \times 10 ^ 9$的复杂度本身就是错误的。要说这也是出题人的问题，既然要放 $\log _ 2 ^ 2$的过就不应该搞 $3 \times 10 ^ 4$的数据范围，搞个 $10 ^ 4$就差不多了，非要开那么大被 hack 也无可厚非吧

搞的我很不愉快主要是莫名其妙就被 diss 了，而且有的同学对待事情太过于较真，恨不得把 Remmina 绑起来挂天花板上没法出数据才最好，只是碰巧的是 Remmina 对于 “卡掉错误算法” 这件事情也很较真（即使 Remmina 特别喜欢写瞎搞玄学算法）

这次有点失态，不过我还是要卡掉 $\log _ 2 ^ 2$的程序