爆零力。

分析

T1

给定 $S=n^n,n\in\mathbb{N^{*}}$ 求 $n$ 。

用的 NTT，OJ 的评测机太慢了，常数爆炸。

正解是当 $n>2$ 时，每一个 $n^n$ 位数都不同，且等于 $\left\lfloor n\log_{10}n\right\rfloor + 1$ ，然后二分。

const int N = 3e5 + 5;

inline ll Read() {
    ll x = 0, f = 1;
    char c = getchar();
    while (c != '-' && (c < '0' || c > '9')) c = getchar();
    if (c == '-')
        f = -f, c = getchar();
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return x * f;
}

namespace NTT {
const ll mod = 998244353ll, G = 3, invG = 332748118ll;
int n, m;
int tr[N << 1];
ll f[N << 1], g[N << 1];

ll qpow(ll a, ll b) {
    ll ans = 1;
    for (; b; b >>= 1, a = a * a % mod) ans = ans * (b & 1 ? a : 1) % mod;
    return ans;
}

void NTT(ll *f, bool isDFT) {
    for (int i = 1; i <= n; i++)
        if (i < tr[i])
            swap(f[i], f[tr[i]]);
    for (int p = 2; p <= n; p <<= 1) {
        int len = p >> 1;
        ll omega = qpow(isDFT ? G : invG, (mod - 1) / p);
        for (int k = 0; k < n; k += p) {
            ll tmp = 1ll;
            for (int i = k; i < k + len; i++) {
                ll y = tmp * f[i + len] % mod;
                f[i + len] = (f[i] - y + mod) % mod;
                f[i] = (f[i] + y) % mod;
                tmp = tmp * omega % mod;
            }
        }
    }
    if (!isDFT) {
        ll invn = qpow(n, mod - 2);
        for (int i = 0; i <= n; i++) f[i] = f[i] * invn % mod;
    }
}

void main(int _n, int _m) {
    n = _n, m = _m;
    for (m += n, n = 1; n <= m; n <<= 1)
        ;
    for (int i = 1; i <= n; i++) tr[i] = (tr[i >> 1] >> 1) | (i & 1 ? n >> 1 : 0);

    NTT(f, 1), NTT(g, 1);

    for (int i = 0; i <= n; i++) f[i] = f[i] * g[i];

    NTT(f, 0);
}
}  // namespace NTT

struct Number {
    int val[N];
    void operator=(int b) {
        for (; val[0]; val[val[0]--] = 0)
            ;
        for (val[0] = 0; b; b /= 10) {
            val[++val[0]] = b % 10;
        }
        return;
    }
    Number operator*(Number b) {
        memset(NTT::f, 0, sizeof NTT::f);
        memset(NTT::g, 0, sizeof NTT::g);
        for (int i = 1; i <= val[0]; i++) NTT::f[i - 1] = val[i];
        for (int i = 1; i <= b.val[0]; i++) NTT::g[i - 1] = b.val[i];
        NTT::main(val[0] - 1, b.val[0] - 1);
        Number c;
        c.val[0] = NTT::m + 1;
        int d = 0, v = 0, maxLen = c.val[0];
        for (int i = 1; i <= c.val[0] || v; i++) {
            d = NTT::f[i - 1] + v;
            c.val[i] = d % 10;
            v = d / 10;
            maxLen = max(maxLen, i);
        }
        c.val[0] = maxLen;
        return c;
    }
} n, tmp;
Number operator^(Number a, int b) {
    Number ans;
    ans = 1;
    for (; b; b >>= 1, a = a * a)
        if (b & 1)
            ans = ans * a;
    return ans;
}

char s[N];
int len;

int check(int x) {
    int tmp = 1.0 * x * log10(x);
    tmp++;
    return tmp > len;
}

int main() {
    //	freopen(".in", "r", stdin);
    //	freopen(".out", "w", stdout);
    scanf("%s", s + 1);
    len = strlen(s + 1);
    if (len == 1 && s[1] == '1') {
        puts("1");
        return 0;
    }
    if (len == 1 && s[1] == '0') {
        puts("0");
        return 0;
    }
    if (len == 1 && s[1] == '4') {
        puts("2");
        return 0;
    }
    int l = 0, r = 65535, ans = 0;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid))
            r = mid - 1;
        else
            l = mid + 1, ans = mid;
    }
    printf("%d\n", ans);
    return 0;
}

T2

动态，在给定点集中，找树的直径。

其中用到 $\mathcal{O}(1)$ LCA，方法是用欧拉序（DFS 序，但重复访问的点重复加入序里）转为序列，然后 ST 表求两点间深度最小的点。

贴个没过的代码：

const int N = 1e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

int n, q;
int head[N], tot;
struct edge {
	int to, nxt;
}e[N << 1];
void Add(int u, int v) {
	e[++tot] = (edge) {v, head[u]}, head[u] = tot;
}
int dep[N], dfn, eln;
int a[N << 1], b[N], f[N][25];
int dpos[N], epos[N];
void dfs(int u, int fa) {
	dep[u] = dep[fa] + 1;
	f[u][0] = u;
	a[++eln] = u;
	b[++dfn] = u;
	dpos[u] = dfn;
	epos[u] = eln;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if (v == fa) continue;
		dfs(v, u);
		a[++eln] = u;
	}
}

int LCA(int u, int v) {
	u = epos[u], v = epos[v];
	if (u > v) u ^= v ^= u ^= v;
	int len = log2(v - u + 1);
	if (dep[f[u][len]] < dep[f[v - (1 << len) + 1][len]]) return f[u][len];
	return f[v - (1 << len) + 1][len];
}
int distance (int u, int v) { return 2 * dep[LCA(u, v)] - dep[u] - dep[v]; }

int type[N];
struct SegmentTree {
	struct Tree {
		int l, r, p[2];
	}t[N << 2];

	void PushUp (int p) {
		int p1, p2, dis = 0, flag = 0;
		if (!type[t[p << 1].p[0]] && !type[t[p << 1].p[1]] && dis < distance(t[p << 1].p[0], t[p << 1].p[1])) dis = distance(t[p << 1].p[0], t[p << 1].p[1]), p1 = t[p << 1].p[0], p2 = t[p << 1].p[1], flag = 1;
		if (!type[t[p << 1 | 1].p[0]] && !type[t[p << 1].p[1]] && dis < distance(t[p << 1 | 1].p[0], t[p << 1].p[1])) dis = distance(t[p << 1 | 1].p[0], t[p << 1].p[1]), p1 = t[p << 1 | 1].p[0], p2 = t[p << 1].p[1], flag = 1;
		if (!type[t[p << 1 | 1].p[0]] && !type[t[p << 1].p[0]] && dis < distance(t[p << 1 | 1].p[0], t[p << 1].p[0])) dis = distance(t[p << 1 | 1].p[0], t[p << 1].p[0]), p1 = t[p << 1 | 1].p[0], p2 = t[p << 1].p[0], flag = 1;
		if (!type[t[p << 1].p[0]] && !type[t[p << 1 | 1].p[1]] && dis < distance(t[p << 1].p[0], t[p << 1 | 1].p[1])) dis = distance(t[p << 1].p[0], t[p << 1 | 1].p[1]), p1 = t[p << 1].p[0], p2 = t[p << 1 | 1].p[1], flag = 1;
		if (!type[t[p << 1].p[1]] && !type[t[p << 1 | 1].p[1]] && dis < distance(t[p << 1].p[1], t[p << 1 | 1].p[1])) dis = distance(t[p << 1].p[1], t[p << 1 | 1].p[1]), p1 = t[p << 1].p[1], p2 = t[p << 1 | 1].p[1], flag = 1;
		if (!type[t[p << 1 | 1].p[0]] && !type[t[p << 1 | 1].p[1]] && dis < distance(t[p << 1 | 1].p[0], t[p << 1 | 1].p[1])) 
			dis = distance(t[p << 1 | 1].p[0], t[p << 1 | 1].p[1]), p1 = t[p << 1 | 1].p[0], p2 = t[p << 1 | 1].p[1], flag = 1;
		if (!flag) {
			if (!type[t[p << 1].p[0]]) p1 = p2 = t[p << 1].p[0], flag = 1;
			if (!type[t[p << 1].p[1]]) p1 = p2 = t[p << 1].p[1], flag = 1;
			if (!type[t[p << 1 | 1].p[0]]) p1 = p2 = t[p << 1 | 1].p[0], flag = 1;
			if (!type[t[p << 1 | 1].p[1]]) p1 = p2 = t[p << 1 | 1].p[1], flag = 1;
		} 
		if (!flag) p1 = p2 = t[p << 1].p[0];
		t[p].p[0] = p1, t[p].p[1] = p2;
	}
	void Build(int p, int l, int r) {
		t[p].l = l, t[p].r = r;
		if (t[p].l == t[p].r) {
			t[p].p[0] = t[p].p[1] = b[t[p].l];
			return;
		}
		int mid = t[p].l + t[p].r >> 1;
		Build (p << 1, l, mid);
		Build (p << 1 | 1, mid + 1, r);
		PushUp(p);
	}
	void Modify(int p, int x) {
		if (t[p].l == t[p].r) {
			type[x] ^= 1;
			return;
		}
		int mid = t[p].l + t[p].r >> 1;
		if (x <= mid) Modify (p << 1, x);
		else Modify (p << 1 | 1, x);
		PushUp(p);
	}
}t;

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	n = Read(), q = Read();
	for (int i = 1; i < n; i++) {
		int u = Read(), v = Read();
		Add(u, v), Add(v, u);
	}
	dfs(1, 0);
	for (int j = 1; j <= 22; j++)
		for (int i = 1; i + (1 << j) <= eln; i++)
			if (dep[f[i][j-1]] < dep[f[i + (1 << j - 1)][j-1]]) f[i][j] = f[i][j-1];
			else f[i][j] = f[i + (1 << j-1)][j-1];
	t.Build(1, 1, n);
//	return 0;
	for (; q--; ) {
		string s;
		cin >> s;
		if (s[0] == 'G') {
			printf ("%d\n", distance(t.t[1].p[0], t.t[1].p[1]));
		} else {
			int x = Read();
			t.Modify(1, b[x]);
		}
	}
	return 0;
}