• 使用 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;
inline void push(int a, int b)
{
}
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;
inline void push(int a, int b)
{
}
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;
}

# 后记

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

#### Remmina

No puzzle that couldn't be solved.