2020杭电第九场

A、Tree 6867

简单题。

#include <bits/stdc++.h>
using ul = std::uint32_t;
using ull = std::uint64_t;
using li = std::int32_t;
using ll = std::int64_t;
ul T;
const ul maxn = 5e5;
ul n;
ul p[maxn + 1];
ul sz[maxn + 1];
ull ans[maxn + 1];
ull mx;
ull out;
int main()
{
    std::scanf("%u", &T);
    for (ul Case = 1; Case <= T; ++Case) {
        std::scanf("%u", &n);
        sz[1] = 1;
        for (ul i = 2; i <= n; ++i) {
            std::scanf("%u", &p[i]);
            sz[i] = 1;
        }
        ans[1] = 0;
        out = 0;
        for (ul i = n; i >= 2; --i) {
            sz[p[i]] += sz[i];
            ans[i] = n - sz[i];
            out += sz[i];
        }
        out += sz[1];
        mx = 0;
        for (ul i = 2; i <= n; ++i) {
            ans[i] += ans[p[i]];
            mx = std::max(mx, ans[i]);
        }
        std::printf("%llu\n", out + mx);
    }
    return 0;
}

B、Absolute Math 6868

题意：$f(x):=\sum_{d|x}\mu^2(d)$，求$\sum_{i=1}^mf(ni)$
设$S:=\{p\in P:p|n\},r_K:=\prod_{p\in K}p$

$$\sum_{i=1}^mf(ni) \\=\sum_{i=1}^m\frac{f(n)f(i)}{\prod_{p\in S}2^{[p|i]}} \\=\sum_{i=1}^m\sum_{M\subset S}\left(\prod_{p\in M}[p|i]\right)\left(\prod_{p\notin M}(1-[p|i])\right)\frac{f(n)f(i)}{2^{|M|}} \\=\sum_{i=1}^m\sum_{t=0}^{|S|}\frac{f(n)f(i)}{2^{t}}\sum_{M\in C_S^t}\left(\prod_{p\in M}[p|i]\right)\left(\prod_{p\notin M}(1-[p|i])\right) \\=\sum_{i=1}^m\sum_{t=0}^{|S|}\frac{f(n)f(i)}{2^{t}}\sum_{k=t}^{|S|}(-1)^{k-t}C_k^t\sum_{K\in C_S^k}\prod_{p\in K}[p|i] \\=\sum_{K\subset S}\sum_{i=1}^m\left(\prod_{p\in K}[p|i]\right)f(n)f(i)\sum_{t=0}^{|K|}(-1)^{|K|-t}C_{|K|}^t\frac{1}{2^t} \\=\sum_{K\subset S}\sum_{j=1}^{\lfloor\frac{m}{r_K}\rfloor}f(n)f(jr_K)\sum_{t=0}^{|K|}(-1)^{|K|-t}C_{|K|}^t\frac{1}{2^t} \\=\sum_{K\subset S}f(n)\sum_{i=1}^{\lfloor\frac{m}{r_K}\rfloor}f(ir_K)(-\frac12)^{|K|}$$
设$g(S,m):=\sum_{i=1}^mf(r_Si)$，于是 $$g(S,m)=f(r_S)\sum_{K\subset S}(-\frac12)^{|K|}g(K,\lfloor\frac{m}{r_K}\rfloor)\\=2^{|S|}\sum_{k\subset S}(-\frac12)^{|K|}g(K,\lfloor\frac{m}{r_K}\rfloor).$$

关于此递推式的时间复杂度，首先，肯定是关于$m$不降的（注意，这句话成立的前提是不针对$\lfloor\frac mt\rfloor$使用记忆化，因为这样可能导致$t$不同的时候$\lfloor\frac mt\rfloor$也相同，但在更小的$m$，却又不相同了，所以用于计算时间复杂度的程序必须要把记忆化改为针对$t$的。然而实际上，如果只是对$t$记忆化，那就根本没必要记忆化，因为实际上根本不可能重复对$t$的调用），所以直接取$m$为$10^7$，然后将$n$全部枚举，可知实际计算步数（指对$g(S,m)$的调用次数）小于等于$58087$，也就是$n=2*3*5*7*11*13*17*19$时的值，故总时间$O(58087T)$。

不使用记忆化的版本：

#include <bits/stdc++.h>
using ul = std::uint32_t;
using li = std::int32_t;
using ull = std::uint64_t;
using ll = std::int64_t;
const ul mod = 1e9 + 7;
ul plus(ul a, ul b)
{
    return a + b < mod ? a + b : a + b - mod;
}
ul minus(ul a, ul b)
{
    return a < b ? a + mod - b : a - b;
}
ul mul(ul a, ul b)
{
    return ull(a) * ull(b) % mod;
}
const ul maxm = 1e7;
const ul maxn = 1e7;
ul f[maxm + 1];
ul sf[maxm + 1];
std::vector<ul> prime;
bool notprime[maxn + 1];
ul low[maxn + 1];
ul n, m;
ul sz[256];
ul r[256];
ul p[8];
ul Case;
ul pow2[9];
ul pow2inv[9];
ul getans(ul s, ull t)
{
    if (m < t) {
        return 0;
    }
    if (s == 0) {
        return sf[m / t];
    }
    ul ans = 0;
    for (ul k = s; ; k = k - 1 & s) {
        if (sz[k] & 1) {
            ans = minus(ans, mul(getans(k, t * r[k]), pow2inv[sz[k]]));
        } else {
            ans = plus(ans, mul(getans(k, t * r[k]), pow2inv[sz[k]]));
        }
        if (k == 0) {
            break;
        }
    }
    ans = mul(ans, pow2[sz[s]]);
    return ans;
}
ul T;
int main()
{
    for (ul i = 1; i != 256; ++i) {
        sz[i] = sz[i >> 1] + (i & 1);
    }
    pow2[0] = pow2inv[0] = 1;
    for (ul i = 1; i <= 8; ++i) {
        pow2[i] = pow2[i - 1] * 2;
        pow2inv[i] = (pow2inv[i - 1] & 1) ? (pow2inv[i - 1] + mod >> 1) : (pow2inv[i - 1] >> 1);
    }
    f[1] = 1;
    sf[1] = 1;
    for (ul i = 2; i <= maxn; ++i) {
        if (!notprime[i]) {
            prime.push_back(i);
            f[i] = 2;
            low[i] = i;
        }
        for (ul p : prime) {
            if (i * p > maxn) {
                break;
            }
            notprime[i * p] = true;
            low[i * p] = p;
            if (i % p == 0) {
                f[i * p] = f[i];
                break;
            } else {
                f[i * p] = 2 * f[i];
            }
        }
        sf[i] = plus(sf[i - 1], f[i]);
    }
    std::scanf("%u", &T);
    for (Case = 1; Case <= T; ++Case) {
        std::scanf("%u%u", &n, &m);
        ul tn = 1;
        ul sn = 0;
        while (n != 1) {
            p[sn] = low[n];
            tn *= p[sn];
            while (low[n] == p[sn]) {
                n /= p[sn];
            }
            ++sn;
        }
        n = tn;
        r[0] = 1;
        for (ul i = 1; i != (1 << sn); ++i) {
            r[i] = r[i & ~(1 << 31 - __builtin_clz(i))] * p[31 - __builtin_clz(i)];
        }
        std::printf("%u\n", getans((1 << sn) - 1, 1));
    }
    return 0;
}

使用记忆化的版本：

#include <bits/stdc++.h>
using ul = std::uint32_t;
using li = std::int32_t;
using ull = std::uint64_t;
using ll = std::int64_t;
const ul mod = 1e9 + 7;
ul plus(ul a, ul b)
{
    return a + b < mod ? a + b : a + b - mod;
}
ul minus(ul a, ul b)
{
    return a < b ? a + mod - b : a - b;
}
ul mul(ul a, ul b)
{
    return ull(a) * ull(b) % mod;
}
const ul maxm = 1e7;
const ul maxn = 1e7;
ul f[maxm + 1];
ul sf[maxm + 1];
std::vector<ul> prime;
bool notprime[maxn + 1];
ul low[maxn + 1];
ul n, m, sq;
ul sz[256];
ul r[256];
ul p[8];
ul Case;
ul ans[7000][256];
ul already[7000][256];
ul pow2[9];
ul pow2inv[9];
ul getans(ul mm, ul s)
{
    ul id;
    if (mm <= sq) {
        id = mm;
    } else {
        id = m / mm + sq + 1;
    }
    if (already[id][s] == Case) {
        return ans[id][s];
    }
    already[id][s] = Case;
    if (mm == 0) {
        return ans[id][s] = 0;
    }
    if (s == 0) {
        return ans[id][s] = sf[mm];
    }
    ans[id][s] = 0;
    for (ul k = s; ; k = k - 1 & s) {
        if (sz[k] & 1) {
            ans[id][s] = minus(ans[id][s], mul(getans(mm / r[k], k), pow2inv[sz[k]]));
        } else {
            ans[id][s] = plus(ans[id][s], mul(getans(mm / r[k], k), pow2inv[sz[k]]));
        }
        if (k == 0) {
            break;
        }
    }
    ans[id][s] = mul(ans[id][s], pow2[sz[s]]);
    return ans[id][s];
}
ul T;
int main()
{
    for (ul i = 1; i != 256; ++i) {
        sz[i] = sz[i >> 1] + (i & 1);
    }
    pow2[0] = pow2inv[0] = 1;
    for (ul i = 1; i <= 8; ++i) {
        pow2[i] = pow2[i - 1] * 2;
        pow2inv[i] = (pow2inv[i - 1] & 1) ? (pow2inv[i - 1] + mod >> 1) : (pow2inv[i - 1] >> 1);
    }
    f[1] = 1;
    sf[1] = 1;
    for (ul i = 2; i <= maxn; ++i) {
        if (!notprime[i]) {
            prime.push_back(i);
            f[i] = 2;
            low[i] = i;
        }
        for (ul p : prime) {
            if (i * p > maxn) {
                break;
            }
            notprime[i * p] = true;
            low[i * p] = p;
            if (i % p == 0) {
                f[i * p] = f[i];
                break;
            } else {
                f[i * p] = 2 * f[i];
            }
        }
        sf[i] = plus(sf[i - 1], f[i]);
    }
    std::scanf("%u", &T);
    for (Case = 1; Case <= T; ++Case) {
        std::scanf("%u%u", &n, &m);
        ul tn = 1;
        ul sn = 0;
        while (n != 1) {
            p[sn] = low[n];
            tn *= p[sn];
            while (low[n] == p[sn]) {
                n /= p[sn];
            }
            ++sn;
        }
        n = tn;
        r[0] = 1;
        for (ul i = 1; i != (1 << sn); ++i) {
            r[i] = r[i & ~(1 << 31 - __builtin_clz(i))] * p[31 - __builtin_clz(i)];
        }
        sq = std::sqrt(m);
        std::printf("%u\n", getans(m, (1 << sn) - 1));
    }
    return 0;
}

C、Slime and Stones 6869

先给出结论，然后证明：一个状态$(x,y)$是必败态，当且仅当

$$\exists m\in\mathbb N,\\(x,y)=\left(\left\lfloor\frac{m(1-k+\sqrt{k^2+2k+5})}2\right\rfloor,\left\lfloor\frac{m(3+k+\sqrt{k^2+2k+5})}2\right\rfloor\right)\\\lor\\(y,x)=\left(\left\lfloor\frac{m(1-k+\sqrt{k^2+2k+5})}2\right\rfloor,\left\lfloor\frac{m(3+k+\sqrt{k^2+2k+5})}2\right\rfloor\right).$$ 今后将$\frac{1-k+\sqrt{k^2+2k+5}}2$记为$S_k$，$\frac{3+k+\sqrt{k^2+2k+5}}2$记为$T_k$。

先说明$S_k$和$T_k$的一些性质：
①$S_k=1+\frac{\sqrt{k^2+2k+5}-(k+1)}2=1+\frac5{2(\sqrt{k^2+2k+5}+k+1)}\geq1$；
②$T_k-S_k=k+1$，亦可知$T_k-\lfloor T_k\rfloor=S_k-\lfloor S_k\rfloor$，亦可知，

$$\forall m\in\mathbb N,T_km-\lfloor T_km\rfloor=S_km-\lfloor S_km\rfloor=:r_m;$$
③因为$S_k$和$T_k$均为正无理数，且$\frac1{S_k}+\frac1{T_k}=1$，故$\{\lfloor mS_k\rfloor:m\in\mathbb N^+\}$和$\{\lfloor mT_k\rfloor:m\in\mathbb N^+\}$互不相交，且并是$\mathbb N^+$。（这一点的证明，见https://www.zybuluo.com/qq290637843/note/1746147）

现在任务就是要证明两点：①必败态不能到达必败态；②必胜态能到达必败态。

1、必败不能到达必败
　　1.1、$(x_1,y_1)$和$(x_2,y_2)$同属于一类：
　　不妨设属于第一类，并设$m_2>m_1$，现在要证明

$$\begin{cases}x_1<x_2,\\y_2-y_1>x_2-x_1+k.\end{cases}$$ 关于第一个命题，由$S_k\geq 1$可知 $$x_1\leq S_km_1\leq S_km_2-1<x_2,$$ 关于第二个命题，由$T_k-S_k=k+1$可知 $$y_2-y_1-x_2+x_1\\=T_km_2-r_{m_2}-T_km_1+r_{m_1}-S_km_2+r_{m_2}+S_km_1-r_{m_1}\\=(m_2-m_1)(k+1)>k.$$
　　1.2、$(x_1,y_1)$和$(x_2,y_2)$不属于同一类：
　　不妨设$(x_1,y_1)$属于第一类，$(x_2,y_2)$属于第二类，于是$m_1$和$m_2$不同时为$0$，现在要证明 $$\begin{cases}x_1\neq x_2,\\y_1\neq y_2,\\y_1-x_1>y_2-x_2+k.\end{cases}$$ 第一和第二个命题实际都是要证明 $$\forall m_1,m_2\in\mathbb N,\lfloor T_km_1\rfloor=\lfloor S_km_2\rfloor\Rightarrow m_1=m_2=0,$$ 而$S_k$和$T_k$的性质③能直接得出这一点。而第三个命题只需要注意到 $$y_1-x_1-y_2+x_2\\=T_km_1-r_{m_1}-S_km_1+r_{m_1}-S_km_2+r_{m_2}+T_km_2-r_{m_2}\\=(m_1+m_2)(k+1)>k.$$
　　
2、必胜能达到必败
　　考虑必胜态$(x,y)$，则存在$(x,y')$和$(x',y)$为必败态（来自性质③）：
　　2.1、$(x,y')$和$(x',y)$均为一类点时：于是 $$\begin{cases}x=S_km_1-r_{m_1},\\y=T_km_2-r_{m_2},\\x'=S_km_2-r_{m_2},\\y'=T_km_1-r_{m_1}.\end{cases}$$ 于是$y>y'$和$x>x'$恰好有一个为真。
　　2.2、$(x,y')$和$(x',y)$均为二类点时：于是 $$\begin{cases}x=T_km_1-r_{m_1},\\y=S_km_2-r_{m_2},\\x'=T_km_2-r_{m_2},\\y'=S_km_1-r_{m_1}.\end{cases}$$ 于是$y>y'$和$x>x'$恰好有一个为真。
　　2.3、$(x,y')$为二类点且$(x',y)$为一类点时：于是 $$\begin{cases}x=T_km_1-r_{m_1},\\y=T_km_2-r_{m_2},\\x'=S_km_2-r_{m_2},\\y'=S_km_1-r_{m_1}.\end{cases}$$ 于是$y>y'$和$x>x'$至少有一个为真。
　　2.4、$(x,y')$为一类点且$(x',y)$为二类点时：于是 $$\begin{cases}x=S_km_1-r_{m_1},\\y=S_km_2-r_{m_2},\\x'=T_km_2-r_{m_2},\\y'=T_km_1-r_{m_1}.\end{cases}$$ ，只需要考虑$x<x'$且$y<y'$的情况。由于性质②，可知，既存在必败态$(x'',y'')$满足$y-x-k\leq y''-x''\leq y-x$，又存在（可能是不同的）必败态$(x'',y'')$满足$y-x\leq y''-x''\leq y-x+k$。如果$y\geq x$，则第一种$(x'',y'')$就是可达到的，如果$x\geq y$，则第二种$(x'',y'')$就是可达到的。
　　
　　顺带$S_k$和$T_k$的连分数形式为$[1,\{k+1\}]$和$[k+2,\{k+1\}]$，可以简化代码，这一点请自己证明。
　　

#include <bits/stdc++.h>
using ul = std::uint32_t;
using li = std::int32_t;
using ull = std::uint64_t;
using ll = std::int64_t;
using lll = __int128;
ul a, b, k;
lll x, y;
ul T;
ull ma, mb;
ull mas, mbt;
lll upper(lll x, lll y)
{
    return (x + y - 1) / y;
}
int main()
{
    std::scanf("%u", &T);
    for (ul Case = 1; Case <= T; ++Case) {
        std::scanf("%u%u%u", &a, &b, &k);
        if (a > b) {
            std::swap(a, b);
        }
        ma = a, mb = upper(b, k + 2);
        mas = a, mbt = mb * lll(k + 2);
        x = 1, y = k + 1;
        while (true) {
            ull tma = upper(lll(a) * y, x + y);
            ull tmb = upper(lll(b) * y, x + y * lll(k + 2));
            ull tmas = lll(tma) * (x + y) / y;
            ull tmbt = lll(tmb) * (x + y * lll(k + 2)) / y;
            if (tma == ma && tmb == mb && tmas == mas && tmbt == mbt) {
                break;
            }
            ma = tma;
            mb = tmb;
            mas = tmas;
            mbt = tmbt;
            x += y * lll(k + 1);
            std::swap(x, y);
        }
        std::printf(ma == mb && mas == a && mbt == b ? "0\n" : "1\n");
    }
    return 0;
}

D、Product 6870

不知道为什么下面的代码就能过，过于肏你妈的调参题。代码中$f(x,y)$是指将小于等于$x$的非负整数被拆为大于等于$y$的质数的和有多少种方案，两个方案等价是指每一个质数出现的次数相同，$y$只取质数，然后借助于$f$用gett()函数实现等概率从所有拆解方案中选一个。

#include <bits/stdc++.h>
using ul = std::uint32_t;
using li = std::int32_t;
using ull = std::uint64_t;
using ll = std::int64_t;
ul T;
ull p, a;
std::mt19937_64 rnd;
std::vector<ul> ans;
bool notprime[2501];
std::vector<ul> prime;
void exgcd(ll a, ll b, ll& x, ll& y)
{
    if (b) {
        exgcd(b, a % b, y, x);
        y -= a / b * x;
    } else {
        x = 1;
        y = 0;
    }
}
ull inverse(ull a)
{
    ll x, y;
    exgcd(a, p, x, y);
    return x < 0 ? x + ll(p) : x;
}
using llf = long double;
ll mul(ll a, ll b, ll p)
{
    ll t = a * b - ll(llf(a) * llf(b) / llf(p)) * p;
    return t < 0 ? t + p : (t < p ? t : t - p);
}
const ul b = 256;
ull f[b + 1][b + b + 1];
ull inv[b + 1][b + 1];
ul vsz = 0;
ul tv[ul(1e8)];
ul sz = 0;
ull ts[ul(1e6)];
ul start[ul(1e6)];
ul next[2501];
void gett()
{
    ts[sz] = 1;
    start[sz] = vsz;
    auto& t = ts[sz];
    ++sz;
    ul x = b, y = 2;
    ull r = rnd() % f[x][y];
    ul prev = 2;
    ul cnt = 0;
    while (x >= y && r) {
        if (r < f[x][next[y]]) {
            y = next[y];
        } else {
            r -= f[x][next[y]];
            x -= y;
            tv[vsz] = y;
            ++vsz;
            if (y != prev) {
                t = mul(t, inv[prev][cnt], p);
                prev = y;
                cnt = 0;
            }
            ++cnt;
        }
    }
    t = mul(t, inv[prev][cnt], p);
}
int main()
{
    rnd.seed(std::time(0));
    std::scanf("%llu", &p);
    ul prev = 1;
    for (ul i = 2; i <= 2500; ++i) {
        if (!notprime[i]) {
            prime.push_back(i);
            next[prev] = i;
            prev = i;
            if (i <= b) {
                for (ull t = 0, q = 1; i * t <= b; ++t, q = mul(i, q, p)) {
                    inv[i][t] = inverse(q);
                }
            }
        }
        for (ul p : prime) {
            if (i * p > 2500) {
                break;
            }
            notprime[i * p] = true;
            if (i % p == 0) {
                break;
            }
        }
    }
    for (ul y = b + b; y >= 2; --y) {
        if (notprime[y]) {
            continue;
        }
        for (ul x = 0; x <= b; ++x) {
            if (x < y) {
                f[x][y] = 1;
                continue;
            }
            if (x >= y) {
                f[x][y] += f[x - y][y];
            }
            if (next[y] <= b + b) {
                f[x][y] += f[x][next[y]];
            }
        }
    }
    std::scanf("%u", &T);
    for (ul Case = 1; Case <= T; ++Case) {
        std::scanf("%llu", &a);
        ul i;
        for (i = 0; ; ++i) {
            if (i == sz) {
                gett();
            }
            ull t = ts[i];
            ul sum = 0;
            ull v = mul(t, a, p);
            ans.resize(0);
            for (ul p : prime) {
                if (p > 40 && v > 1e15 || p > 120 && v > 1e13) {
                    break;
                }
                if (sum + p > 2500 - b) {
                    break;
                }
                while (v % p == 0) {
                    v /= p;
                    ans.push_back(p);
                    sum += p;
                }
                if (sum > 2500 - b || v == 1) {
                    break;
                }
            }
            if (v == 1 && sum + b <= 2500) {
                break;
            }
        }
        for (ul k = start[i]; k != start[i + 1] && k != vsz; ++k) {
            ans.push_back(tv[k]);
        }
        std::printf("%u", ul(ans.size()));
        for (auto t : ans) {
            std::printf(" %u", t);
        }
        std::putchar('\n');
    }
    return 0;
}

E、Resistance 6871

圈上边的贡献如下，这是一个大小为$k$的圈。

$$\sum_{i=1}^k\sum_{j=i}^kc_ic_j\frac{(j-i)(k-j+i)}{k} \\=\frac1k\sum_{i=1}^k\sum_{j=i}^kc_ic_j(kj-ki-j^2-i^2+2ij) \\=\sum_{i=1}^kc_i\sum_{j=i}^kjc_j-\sum_{i=1}^kic_i\sum_{j=i}^kc_j-\frac1k\sum_{i=1}^kc_i\sum_{j=i}^kj^2c_j-\frac1k\sum_{i=1}^ki^2c_i\sum_{j=i}^kc_j+\frac2k\sum_{i=1}^kic_i\sum_{j=i}^kjc_j.$$
注意，这个代码在本地跑可能会爆栈。

#include <bits/stdc++.h>
using ul = std::uint32_t;
using li = std::int32_t;
using ull = std::uint64_t;
using ll = std::int64_t;
ul T;
const ul maxn = 2e5;
const ul maxm = 4e5;
ul n, m;
class edge_t {
public:
    ul u = 0;
    ul v = 0;
    ul unext = 0;
    ul vnext = 0;
    ul& next(ul x) {
        return x == u ? unext : vnext;
    }
    ul to(ul x) const {
        return x ^ u ^ v;
    }
    ul next(ul x) const {
        return x == u ? unext : vnext;
    }
};
edge_t edge[maxm + 1];
ul head[maxn + 1];
ul sz[maxn + 1];
ul al[maxn + 1];
ul ale[maxm + 1];
ul back[maxn + 1];
ul p[maxn + 1];
bool incircle[maxn + 1];
void search(ul x)
{
    al[x] = true;
    sz[x] = 1;
    for (ul eid = head[x]; eid; eid = edge[eid].next(x)) {
        if (ale[eid]) {
            continue;
        }
        ale[eid] = true;
        ul y = edge[eid].to(x);
        if (al[y]) {
            back[x] = y;
            for (ul i = x; i != y; i = p[i]) {
                incircle[i] = true;
            }
            continue;
        }
        p[y] = x;
        search(y);
        sz[x] += sz[y];
    }
}
const ul mod = 1e9 + 7;
ul plus(ul a, ul b)
{
    return a + b < mod ? a + b : a + b - mod;
}
ul minus(ul a, ul b)
{
    return a < b ? a + mod - b : a - b;
}
ul mul(ul a, ul b)
{
    return ull(a) * ull(b) % mod;
}
void exgcd(li a, li b, li& x, li& y)
{
    if (b) {
        exgcd(b, a % b, y, x);
        y -= a / b * x;
    } else {
        x = 1;
        y = 0;
    }
}
ul inverse(ul a)
{
    li x, y;
    exgcd(a, mod, x, y);
    return x < 0 ? x + li(mod) : x;
}
ul c[maxn + 1];
ul sumc[maxn + 1];
ul sumjc[maxn + 1];
ul sumjjc[maxn + 1];
int main()
{
    std::scanf("%u", &T);
    for (ul Case = 1; Case <= T; ++Case) {
        std::scanf("%u%u", &n, &m);
        for (ul i = 1; i <= n; ++i) {
            head[i] = 0;
            al[i] = false;
            incircle[i] = false;
            back[i] = 0;
        }
        for (ul i = 1; i <= m; ++i) {
            ale[i] = false;
            std::scanf("%u%u", &edge[i].u, &edge[i].v);
            for (ul x : {edge[i].u, edge[i].v}) {
                edge[i].next(x) = head[x];
                head[x] = i;
            }
        }
        search(1);
        ul ans = 0;
        for (ul i = 2; i <= n; ++i) {
            if (!incircle[i]) {
                ans = plus(ans, mul(sz[i], n - sz[i]));
            }
        }
        for (ul t = 2; t <= n; ++t) {
            if (back[t]) {
                ul k = 0;
                for (ul i = 1, s = t; ; ++i, s = p[s]) {
                    c[i] = sz[s];
                    if (s == back[t]) {
                        k = i;
                        break;
                    }
                }
                for (ul i = k; i >= 2; --i) {
                    c[i] -= c[i - 1];
                }
                c[k] += n - sz[back[t]];
                sumc[k] = c[k];
                sumjc[k] = mul(k, c[k]);
                sumjjc[k] = mul(mul(k, k), c[k]);
                for (ul j = k - 1; j >= 1; --j) {
                    sumc[j] = plus(c[j], sumc[j + 1]);
                    sumjc[j] = plus(mul(j, c[j]), sumjc[j + 1]);
                    sumjjc[j] = plus(mul(mul(j, j), c[j]), sumjjc[j + 1]);
                }
                ul invk = inverse(k);
                for (ul i = 1; i <= k; ++i) {
                    ans = plus(ans, mul(c[i], sumjc[i]));
                    ans = minus(ans, mul(mul(i, c[i]), sumc[i]));
                    ans = minus(ans, mul(invk, mul(c[i], sumjjc[i])));
                    ans = minus(ans, mul(invk, mul(mul(mul(i, i), c[i]), sumc[i])));
                    ans = plus(ans, mul(mul(2, invk), mul(mul(i, c[i]), sumjc[i])));
                }
            }
        }
        std::printf("%u\n", ans);
    }
    return 0;
}

F、Skyscrapers 6872

先重复清洗每个格子可能填的数，直到没有变化为止，接着，舞蹈链搜索。

#include <bits/stdc++.h>
using ul = std::uint32_t;
using li = std::int32_t;
using ull = std::uint64_t;
using ll = std::int64_t;
const ul maxn = 8;
const ul facmaxn = 40320;
ul n;
ul hash[maxn + 1];
std::vector<ul> able[maxn + 1][maxn + 1][maxn + 1];
bool ablev1[maxn + 1][maxn + 1][maxn + 1];
bool ablev2[maxn + 1][maxn + 1][maxn + 1];
std::vector<ul> ablev3[maxn + 1];
std::vector<ul> ablev4[maxn + 1];
std::vector<ul> tmp;
ul idtoper[maxn + 1][facmaxn + 1][maxn + 1];
ul per[maxn + 1];
ul T;
ul t[maxn + 1], b[maxn + 1], l[maxn + 1], r[maxn + 1];
class dlxnode {
public:
    ul left = 0;
    ul right = 0;
    ul up = 0;
    ul down = 0;
    ul col = 0;
    ul row = 0;
    dlxnode()=default;
};
ul dlxsz = 0;
dlxnode dlx[ul(1e6)];
const ul head = 1;
std::vector<ul> ans;
std::vector<ul> currcol;
std::vector<ul> delv;
void init() {
    dlx[head].left = head;
    dlx[head].right = head;
    dlxsz = 1;
    delv.resize(0);
    currcol.resize(0);
    ans.resize(0);
}
ul c[maxn + maxn + maxn * maxn * 5 + maxn * maxn + maxn * maxn + maxn * maxn + maxn * maxn * 5 + maxn * maxn * 5 + maxn * maxn + maxn * maxn + maxn * maxn * maxn * 2 + 1];
const ul sz = 1 << 12;
ul cnt[sz << 1];
ul mnid[sz << 1];
void change(ul pos, ul v)
{
    for (cnt[pos |= sz] += v, pos >>= 1; pos; pos >>= 1) {
        cnt[pos] = std::min(cnt[pos << 1], cnt[pos << 1 | 1]);
        mnid[pos] = cnt[pos << 1] < cnt[pos << 1 | 1] ? mnid[pos << 1] : mnid[pos << 1 | 1];
    }
}
void pushc(ul col)
{
    ++dlxsz;
    dlx[dlxsz].left = dlx[head].left;
    dlx[dlxsz].right = head;
    dlx[head].left = dlxsz;
    dlx[dlx[dlxsz].left].right = dlxsz;
    dlx[dlxsz].up = dlxsz;
    dlx[dlxsz].down = dlxsz;
    dlx[dlxsz].col = col;
    dlx[dlxsz].row = 0;
    c[col] = dlxsz;
}
ul front;
void push(ul row, ul col)
{
    change(col, 1);
    ++dlxsz;
    if (!front) {
        dlx[dlxsz].left = dlxsz;
        dlx[dlxsz].right = dlxsz;
        front = dlxsz;
    } else {
        dlx[dlxsz].left = dlx[front].left;
        dlx[dlxsz].right = front;
        dlx[front].left = dlxsz;
        dlx[dlx[dlxsz].left].right = dlxsz;
    }
    dlx[dlxsz].up = dlx[c[col]].up;
    dlx[dlxsz].down = c[col];
    dlx[c[col]].up = dlxsz;
    dlx[dlx[dlxsz].up].down = dlxsz;
    dlx[dlxsz].row = row;
    dlx[dlxsz].col = col;
}
void del(ul x)
{
    change(dlx[x].col, ~ul(0));
    dlx[dlx[x].right].left = dlx[x].left;
    dlx[dlx[x].left].right = dlx[x].right;
    dlx[dlx[x].up].down = dlx[x].down;
    dlx[dlx[x].down].up = dlx[x].up;
}
void re(ul x)
{
    change(dlx[x].col, 1);
    dlx[dlx[x].right].left = x;
    dlx[dlx[x].left].right = x;
    dlx[dlx[x].up].down = x;
    dlx[dlx[x].down].up = x;
}
bool search()
{
    if (dlx[head].right == head) {
        return true;
    }
    ul co = c[mnid[1]];
    if (dlx[co].down == co) {
        return false;
    }
    currcol.push_back(0);
    for (ul i = dlx[co].up; i != co; i = dlx[i].up) {
        currcol.push_back(i);
    }
    delv.push_back(0);
    for (ul i = dlx[co].down; ; i = dlx[i].down) {
        delv.push_back(i);
        del(i);
        if (i == co) {
            break;
        }
    }
    while (currcol.back()) {
        delv.push_back(0);
        ul choice = currcol.back();
        ans.push_back(dlx[choice].row);
        currcol.pop_back();
        ul tmp = dlx[choice].right;
        if (tmp != choice) {
            for (ul i = dlx[tmp].right; ; i = dlx[i].right) {
                for (ul j = dlx[i].down; ; j = dlx[j].down) {
                    if (j == c[dlx[i].col]) {
                        delv.push_back(j);
                        del(j);
                        continue;
                    }
                    if (j == i) {
                        delv.push_back(j);
                        del(j);
                        break;
                    }
                    for (ul k = dlx[j].right; ; k = dlx[k].right) {
                        delv.push_back(k);
                        del(k);
                        if (k == j) {
                            break;
                        }
                    }
                }
                if (i == tmp) {
                    break;
                }
            }
        }
        if (search()) {
            return true;
        }
        while (delv.back()) {
            re(delv.back());
            delv.pop_back();
        }
        delv.pop_back();
        ans.pop_back();
    }
    currcol.pop_back();
    while (delv.back()) {
        re(delv.back());
        delv.pop_back();
    }
    delv.pop_back();
    return false;
}
int main()
{
    for (ul i = 1, j = 0; i <= 8; ++j) {
        if (__builtin_popcount(j) == 2) {
            hash[i] = j;
            ++i;
        }
    }
    for (ul n = 4; n <= 8; ++n) {
        for (ul i = 1; i <= n; ++i) {
            per[i] = i;
        }
        for (ul id = 1; ; ++id) {
            std::memcpy(idtoper[n][id] + 1, per + 1, n * sizeof(ul));
            ul cntl = 0, cntr = 0;
            ul mx = 0;
            for (ul i = 1; i <= n; ++i) {
                if (per[i] > mx) {
                    mx = per[i];
                    ++cntl;
                }
            }
            mx = 0;
            for (ul i = n; i >= 1; --i) {
                if (per[i] > mx) {
                    mx = per[i];
                    ++cntr;
                }
            }
            able[n][cntl][cntr].push_back(id);
            able[n][0][cntr].push_back(id);
            able[n][cntl][0].push_back(id);
            able[n][0][0].push_back(id);
            if (!std::next_permutation(per + 1, per + n + 1)) {
                break;
            }
        }
    }
    std::scanf("%u", &T);
    for (ul Case = 1; Case <= T; ++Case) {
        std::scanf("%u", &n);
        ul facn = 1;
        for (ul i = 1; i <= n; ++i) {
            facn *= i;
        }
        for (ul i = 1; i <= n; ++i) {
            std::scanf("%u", &t[i]);
        }
        for (ul i = 1; i <= n; ++i) {
            std::scanf("%u", &b[i]);
        }
        for (ul i = 1; i <= n; ++i) {
            std::scanf("%u", &l[i]);
        }
        for (ul i = 1; i <= n; ++i) {
            std::scanf("%u", &r[i]);
        }
        for (ul i = 1; i <= n; ++i) {
            ablev3[i] = able[n][l[i]][r[i]];
            ablev4[i] = able[n][t[i]][b[i]];
        }
        while (true) {
            ul prevcnt = 0;
            for (ul i = 1; i <= n; ++i) {
                for (ul j = 1; j <= n; ++j) {
                    for (ul v = 1; v <= n; ++v) {
                        ablev1[i][j][v] = ablev2[i][j][v] = false;
                    }
                }
            }
            for (ul i = 1; i <= n; ++i) {
                for (ul j : ablev3[i]) {
                    for (ul k = 1; k <= n; ++k) {
                        ablev1[i][k][idtoper[n][j][k]] = true;
                    }
                    ++prevcnt;
                }
            }
            for (ul i = 1; i <= n; ++i) {
                for (ul j : ablev4[i]) {
                    for (ul k = 1; k <= n; ++k) {
                        ablev2[k][i][idtoper[n][j][k]] = true;
                    }
                    ++prevcnt;
                }
            }
            ul currcnt = 0;
            for (ul i = 1; i <= n; ++i) {
                tmp.resize(0);
                for (ul j : ablev3[i]) {
                    bool flag = true;
                    for (ul k = 1; k <= n; ++k) {
                        ul v = idtoper[n][j][k];
                        if (!ablev1[i][k][v] || !ablev2[i][k][v]) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) {
                        tmp.push_back(j);
                        ++currcnt;
                    }
                }
                std::swap(tmp, ablev3[i]);
            }
            for (ul i = 1; i <= n; ++i) {
                tmp.resize(0);
                for (ul j : ablev4[i]) {
                    bool flag = true;
                    for (ul k = 1; k <= n; ++k) {
                        ul v = idtoper[n][j][k];
                        if (!ablev1[k][i][v] || !ablev2[k][i][v]) {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) {
                        tmp.push_back(j);
                        ++currcnt;
                    }
                }
                std::swap(tmp, ablev4[i]);
            }
            if (currcnt == prevcnt) {
                break;
            }
        }
        init();
        for (ul i = 1; i <= (sz << 1) - 1; ++i) {
            mnid[i] = 0;
            cnt[i] = ~ul(0);
        }
        for (ul i = 1; i <= n + n + n * n * 5 + n * n + n * n + n * n + n * n * 5 + n * n * 5 + n * n + n * n + n * n * n * 2; ++i) {
            mnid[i | sz] = i;
            pushc(i);
            cnt[i | sz] = 0;
        }
        for (ul i = 1; i <= n; ++i) {
            for (ul j : ablev3[i]) {
                front = 0;
                ul row = (i - 1) * facn + j;
                ul s = 0;
                push(row, s + i);
                s = n + n;
                for (ul k = 1; k <= n; ++k) {
                    ul v = idtoper[n][j][k];
                    for (ul m = 0; m != 5; ++m) {
                        if (hash[v] >> m & 1) {
                            push(row, s + ((i - 1) * n + k - 1) * 5 + m + 1);
                        }
                    }
                }
                s = n + n + n * n * 5;
                for (ul k = 1; k <= n; ++k) {
                    ul v = idtoper[n][j][k];
                    push(row, s + (k - 1) * n + v);
                }
                s = n + n + n * n * 5 + n * n + n * n + n * n;
                for (ul k = 1; k <= n; ++k) {
                    ul v = idtoper[n][j][k];
                    for (ul m = 0; m != 5; ++m) {
                        if (hash[v] >> m & 1) {
                            push(row, s + ((i - 1) * n + k - 1) * 5 + m + 1);
                        }
                    }
                }
                s = n + n + n * n * 5 + n * n + n * n + n * n + n * n * 5 + n * n * 5 + n * n + n * n;
                for (ul k = 1; k <= n; ++k) {
                    ul v = idtoper[n][j][k];
                    push(row, s + (i - 1) * n * n + (k - 1) * n + v);
                }
            }
        }
        for (ul i = 1; i <= n; ++i) {
            for (ul j : ablev4[i]) {
                front = 0;
                ul row = (n + i - 1) * facn + j;
                ul s = n;
                push(row, s + i);
                s = n + n;
                for (ul k = 1; k <= n; ++k) {
                    ul v = idtoper[n][j][k];
                    for (ul m = 0; m != 5; ++m) {
                        if (~hash[v] >> m & 1) {
                            push(row, s + ((k - 1) * n + i - 1) * 5 + m + 1);
                        }
                    }
                }
                s = n + n + n * n * 5 + n * n;
                for (ul k = 1; k <= n; ++k) {
                    ul v = idtoper[n][j][k];
                    push(row, s + (k - 1) * n + v);
                }
                s = n + n + n * n * 5 + n * n + n * n + n * n + n * n * 5;
                for (ul k = 1; k <= n; ++k) {
                    ul v = idtoper[n][j][k];
                    for (ul m = 0; m != 5; ++m) {
                        if (hash[v] >> m & 1) {
                            push(row, s + ((k - 1) * n + i - 1) * 5 + m + 1);
                        }
                    }
                }
                s = n + n + n * n * 5 + n * n + n * n + n * n + n * n * 5 + n * n * 5 + n * n + n * n + n * n * n;
                for (ul k = 1; k <= n; ++k) {
                    ul v = idtoper[n][j][k];
                    push(row, s + (k - 1) * n * n + (i - 1) * n + v);
                }
            }
        }
        for (ul i = 1; i <= n; ++i) {
            for (ul j = 1; j <= n; ++j) {
                for (ul v = 1; v <= n; ++v) {
                    if (!ablev1[i][j][v] || !ablev2[i][j][v]) {
                        continue;
                    }
                    front = 0;
                    ul row = (n + n) * facn + (i - 1) * n * n + (j - 1) * n + v;
                    ul s = n + n + n * n * 5 + n * n + n * n;
                    push(row, s + (i - 1) * n + j);
                    s = n + n + n * n * 5 + n * n + n * n + n * n;
                    for (ul m = 0; m != 5; ++m) {
                        if (~hash[v] >> m & 1) {
                            push(row, s + ((i - 1) * n + j - 1) * 5 + m + 1);
                        }
                    }
                    s = n + n + n * n * 5 + n * n + n * n + n * n + n * n * 5;
                    for (ul m = 0; m != 5; ++m) {
                        if (~hash[v] >> m & 1) {
                            push(row, s + ((i - 1) * n + j - 1) * 5 + m + 1);
                        }
                    }
                    s = n + n + n * n * 5 + n * n + n * n + n * n + n * n * 5 + n * n * 5;
                    push(row, s + (i - 1) * n + v);
                    s = n + n + n * n * 5 + n * n + n * n + n * n + n * n * 5 + n * n * 5 + n * n;
                    push(row, s + (j - 1) * n + v);
                    s = n + n + n * n * 5 + n * n + n * n + n * n + n * n * 5 + n * n * 5 + n * n + n * n;
                    for (ul k = 1; k <= n; ++k) {
                        if (k == i) {
                            continue;
                        }
                        push(row, s + (k - 1) * n * n + (j - 1) * n + v);
                    }
                    s = n + n + n * n * 5 + n * n + n * n + n * n + n * n * 5 + n * n * 5 + n * n + n * n + n * n * n;
                    for (ul k = 1; k <= n; ++k) {
                        if (k == j) {
                            continue;
                        }
                        push(row, s + (i - 1) * n * n + (k - 1) * n + v);
                    }
                }
            }
        }
        search();
        std::sort(ans.begin(), ans.end());
        for (ul a : ans) {
            if (a > n * facn) {
                continue;
            }
            ul id = (a - 1) % facn + 1;
            for (ul i = 1; i <= n; ++i) {
                if (i != 1) {
                    std::putchar(' ');
                }
                std::printf("%u", idtoper[n][id][i]);
            }
            std::putchar('\n');
        }
    }
    return 0;
}

G、Game 6873

很裸的平衡树，直接用无旋树堆就能过。

#include <bits/stdc++.h>
using ul = std::uint32_t;
using li = std::int32_t;
using ull = std::uint64_t;
using ll = std::int64_t;
ul T;
ul n, q;
const ul maxn = 2e5;
std::mt19937_64 rnd;
class node {
public:
    ul lc = 0;
    ul rc = 0;
    ul sz = 0;
    ul mn = 0;
    ul val = 0;
    ull sum = 0;
    ull rank = 0;
    node()=default;
    void init() {
        *this = node();
        mn = ~ul(0);
        rank = rnd();
    }
};
node tree[maxn + 1];
void update(ul x)
{
    tree[x].sz = tree[tree[x].lc].sz + tree[tree[x].rc].sz + 1;
    tree[x].mn = std::min(std::min(tree[tree[x].lc].mn, tree[tree[x].rc].mn), tree[x].val);
    tree[x].sum = tree[tree[x].lc].sum + tree[tree[x].rc].sum + tree[x].val;
}
void split(ul root, ul& a, ul& b, ul pos)
{
    if (!root) {
        a = b = 0;
        return;
    }
    if (tree[tree[root].lc].sz + 1 < pos) {
        pos -= tree[tree[root].lc].sz + 1;
        a = root;
        split(tree[root].rc, tree[a].rc, b, pos);
    } else {
        b = root;
        split(tree[root].lc, a, tree[b].lc, pos);
    }
    update(root);
}
void merge(ul& root, ul a, ul b)
{
    if (!a || !b) {
        root = a ^ b;
        return;
    }
    if (tree[a].rank > tree[b].rank) {
        root = a;
        merge(tree[root].rc, tree[a].rc, b);
    } else {
        root = b;
        merge(tree[root].lc, a, tree[b].lc);
    }
    update(root);
}
ul queryval(ul root, ul pos)
{
    for ( ; ; ) {
        if (tree[tree[root].lc].sz + 1 < pos) {
            pos -= tree[tree[root].lc].sz + 1;
            root = tree[root].rc;
        } else if (tree[tree[root].lc].sz >= pos) {
            root = tree[root].lc;
        } else {
            return tree[root].val;
        }
    }
}
ul querypos(ul root, ul val)
{
    ul ret = 0;
    if (tree[root].mn >= val) {
        return 0;
    }
    for ( ; ; ) {
        if (tree[tree[root].rc].mn < val) {
            ret += tree[tree[root].lc].sz + 1;
            root = tree[root].rc;
        } else if (tree[root].val < val) {
            ret += tree[tree[root].lc].sz + 1;
            return ret;
        } else {
            root = tree[root].lc;
        }
    }
}
int main()
{
    rnd.seed(std::time(0));
    std::scanf("%u", &T);
    for (ul Case = 1; Case <= T; ++Case) {
        std::scanf("%u%u", &n, &q);
        ul root = 0;
        tree[root].init();
        for (ul i = 1; i <= n; ++i) {
            tree[i].init();
            std::scanf("%u", &tree[i].val);
            update(i);
            merge(root, root, i);
        }
        for (ul i = 1; i <= q; ++i) {
            ul t;
            std::scanf("%u", &t);
            if (t == 1) {
                ul x, y;
                std::scanf("%u%u", &x, &y);
                ul a, e;
                split(root, a, e, x + 1);
                ul keypos = querypos(a, y);
                if (keypos == x || keypos == 0) {
                    std::printf("0\n");
                    merge(root, a, e);
                    continue;
                }
                ul b, c, d;
                split(a, a, c, keypos + 2);
                split(a, a, d, keypos + 1);
                split(a, a, b, keypos);
                ull ans = tree[c].sum + tree[d].sum - ull(tree[c].sz + tree[d].sz) * ull(y - 1);
                tree[b].val += tree[d].val - y + 1;
                update(b);
                tree[d].val = y - 1;
                update(d);
                merge(root, a, b);
                merge(root, root, c);
                merge(root, root, d);
                merge(root, root, e);
                std::printf("%llu\n", ans);
            } else if (t == 2) {
                ul x;
                std::scanf("%u", &x);
                std::printf("%u\n", queryval(root, x));
            }
        }
        for (ul i = 1; i <= n; ++i) {
            if (i != 1) {
                std::putchar(' ');
            }
            std::printf("%u", queryval(root, i));
        }
        std::putchar('\n');
    }
    return 0;
}

H、Distance 6874

　　为了连贯性，用$\sum_{i=a}^bx_i（a>b）$表示$-\sum_{i=b+1}^{a-1}x_i$。
　　设$f(l,r):=\frac12\sum_{i=l}^r\sum_{j=l}^r dis(i,j)$，首先考虑莫队把$(l,r)$排序（按照$\frac{n}{\sqrt m}$对$l$分段，每一段内$r$按照从小到大排序即可）。直接这么做，时间复杂度是$O(n\sqrt m\log^2n)$（$\log^2n$来自重链剖分套线段树的查询和修改），需要继续降低时间。接着，注意（设$g(l_1,r_1,l_2,r_2):=\sum_{i=l_1}^{r_1}\sum_{j=l_2}^{r_2}dis(i,j)$）：

$$f(l_2,r_2)-f(l_1,r_1) \\=f(l_2,r_2)-f(l_2,r_1)+f(l_2,r_1)-f(l_1,r_1) \\=\sum_{i=r_1}^{r_2-1}(f(l_2,i+1)-f(l_2,i))+\sum_{i=l_1}^{l_2-1}(f(i+1,r_1)-f(i,r_1)) \\=\sum_{i=r_1}^{r_2-1}g(l_2,i,i+1,i+1)-\sum_{i=l_1}^{l_2-1}g(i,i,i,r_1) \\=\sum_{i=r_1}^{r_2-1}g(1,i,i+1,i+1)-\sum_{i=r_1}^{r_2-1}g(1,l_2-1,i+1,i+1)-\sum_{i=l_1}^{l_2-1}g(i,i,i,n)+\sum_{i=l_1}^{l_2-1}g(i,i,r_1+1,n) \\=\sum_{i=r_1+1}^{r_2}g(1,i,i,i)-\sum_{i=r_1+1}^{r_2}g(1,l_2-1,i,i)-\sum_{i=l_1}^{l_2-1}g(i,i,i,n)+\sum_{i=l_1}^{l_2-1}g(i,i,r_1+1,n).$$
其中第一和第三个求和中所需要计算的项，可以在$O(n)$次修改以及查询中完成，而第二和第四个求和中，根据莫队的特性可知，一共要算$O(n\sqrt m)$个结果，总共需要$O(n\sqrt m)$次查询，修改则需要$O(n)$次。由此可知，总计需要$O(n\sqrt m)$次查询，$O(n)$次修改。
“所以要求修改$O(\sqrt n)$要完成，查询$O(1)$要完成，这样就能让总时间复杂度为$O(n(\sqrt m+\sqrt n))$，直接对树根号分块即可。”
引号中的话是官方题解翻译过来的结果，但我实在不知道怎样分块能做到这么好的程度，最终选择重链剖分套根号分块。于是总时间复杂度为$O(n\sqrt m\log n+n\sqrt{n\log n})$，关于为什么第二个$\log$在根号里边，请自行证明。直接这样还是会超时的，接着，注意到二次离线莫队将允许像写广搜动态规划那样转移，所以实际询问次数可以压缩到最小生成树的大小，这样常数就很小了。（其实原则上可以更小，因为是允许辅助点的，所以是斯坦纳树）。

#include <bits/stdc++.h>
using ul = std::uint32_t;
using li = std::int32_t;
using ull = std::uint64_t;
using ll = std::int64_t;
ul T;
ul n, m;
const ul maxn = 2e5;
const ul maxm = 2e5;
class edge_t {
public:
    ul to = 0;
    ul d = 0;
    edge_t(ul a, ul b): to(a), d(b) {}
    edge_t()=default;
};
std::vector<edge_t> edge[maxn + 1];
ul p[maxn + 1];
ul bigc[maxn + 1];
ul depth[maxn + 1];
ul sz[maxn + 1];
ul dfn[maxn + 1];
ul rdfn[maxn + 1];
ul hvhd[maxn + 1];
ul hvlen[maxn + 1];
ul hvb[maxn + 1];
ul hvbdfn[maxn + 1];
ul rdfnhvhddfn[maxn + 1];
ul rdfnphvhddfn[maxn + 1];
ul depthdfn[maxn + 1];
ul hvlendfn[maxn + 1];
ul lambda[maxn + 1];
ul alpha[maxn + 1];
ul as[maxn + 1];
ul bs[maxn + 1];
ul ap[maxn + 1];
ul bp[maxn + 1];
ul sd;
ul cnt;
void search1(ul curr)
{
    sz[curr] = 1;
    const ul prev = p[curr];
    bigc[curr] = 0;
    for (const auto &e : edge[curr]) {
        ul next = e.to;
        ul d = e.d;
        if (next == prev) {
            continue;
        }
        depth[next] = depth[curr] + d;
        p[next] = curr;
        search1(next);
        sz[curr] += sz[next];
        if (!bigc[curr] || sz[next] > sz[bigc[curr]]) {
            bigc[curr] = next;
        }
    }
}
ul tim = 0;
void search2(ul curr)
{
    ++tim;
    rdfn[curr] = tim;
    dfn[tim] = curr;
    rdfnhvhddfn[tim] = rdfn[hvhd[curr]];
    rdfnphvhddfn[tim] = rdfn[p[hvhd[curr]]];
    depthdfn[tim] = depth[curr];
    lambda[tim] = depth[curr] - depth[dfn[rdfnphvhddfn[tim]]];
    if (bigc[curr]) {
        hvhd[bigc[curr]] = hvhd[curr];
        ++hvlen[hvhd[curr]];
        search2(bigc[curr]);
    }
    ul prev = p[curr];
    for (const auto &e : edge[curr]) {
        ul next = e.to;
        if (next == prev || next == bigc[curr]) {
            continue;
        }
        hvhd[next] = next;
        hvlen[next] = 1;
        search2(next);
    }
    hvlendfn[rdfn[curr]] = hvlen[curr];
}
void insert(ul x)
{
    sd += depth[x];
    ++cnt;
    ul rx = rdfn[x];
    while (rx) {
        ul rh = rdfnhvhddfn[rx];
        ul dis = depthdfn[rx] - depthdfn[rdfnphvhddfn[rx]];
        ul len = hvlendfn[rh];
        ul b = hvbdfn[rh];
        ul q = (rx - rh) / b;
        ul r = (rx - rh) % b;
        for (ul i = 0, j = rh; i != q; ++i, j += b) {
            ++as[j];
        }
        for (ul i = 0, j = rh + q * b; i != r; ++i, ++j) {
            ++ap[j];
        }
        for (ul i = r, j = rh + q * b + r; j != rh + len && i != b; ++i, ++j) {
            bp[j] += dis;
        }
        for (ul i = q + 1, j = rh + (q + 1) * b; j < rh + len; ++i, j += b) {
            bs[j] += dis;
        }
        rx = rdfnphvhddfn[rx];
    }
}
ul query(ul x)
{
    ul r = rdfn[x];
    ul ret = depth[x] * cnt + sd;
    while (r) {
        ul alphar = alpha[r];
        ret -= (as[alphar] + ap[r]) * lambda[r] + bs[alphar] + bp[r] << 1;
        r = rdfnphvhddfn[r];
    }
    return ret;
}
void init(ul n)
{
    sd = 0;
    cnt = 0;
    for (ul i = 1; i <= n; ++i) {
        as[i] = ap[i] = bs[i] = bp[i] = 0;
    }
}
class query_t {
public:
    ul l = 0;
    ul r = 0;
    ul val = 0;
};
query_t qs[maxm + 1];
std::vector<std::pair<li, std::pair<ul, ul>>> cs[maxn + 2];
ul sum[maxn + 2];
class vec {
public:
    li x = 0;
    li y = 0;
    vec()=default;
    vec(li a, li b): x(a), y(b) {}
};
vec operator+(const vec& a, const vec& b)
{
    return vec(a.x + b.x, a.y + b.y);
}
vec operator-(const vec& a, const vec& b)
{
    return vec(a.x - b.x, a.y - b.y);
}
li norm(const vec& a)
{
    return (a.x < 0 ? -a.x : a.x) + (a.y < 0 ? -a.y : a.y);
}
li operator*(const vec& a, const vec& b)
{
    return a.x * b.x + a.y * b.y;
}
vec operator*(const vec& a, li b)
{
    return vec(a.x * b, a.y * b);
}
vec querypoint[maxm + 1];
std::vector<ul> mintree[maxm + 1];
ul fa[maxm + 1];
ul rk[maxm + 1];
ul getfather(ul x)
{
    return fa[x] == x ? x : fa[x] = getfather(fa[x]);
}
bool connect(ul x, ul y)
{
    x = getfather(x);
    y = getfather(y);
    if (x == y) {
        return false;
    }
    if (rk[x] > rk[y]) {
        fa[y] = x;
    } else if (rk[y] > rk[x]) {
        fa[x] = y;
    } else {
        fa[x] = y;
        ++rk[y];
    }
    return true;
}
const ul segsz = 1 << 19;
ul segtree[segsz << 1];
void change(ul pos, ul id, const li w[])
{
    assert(pos >= 1 && pos <= segsz - 1);
    pos |= segsz;
    if (w[segtree[pos]] <= w[id]) {
        return;
    }
    for (segtree[pos] = id, pos >>= 1; pos; pos >>= 1) {
        ul next = w[segtree[pos << 1]] < w[segtree[pos << 1 | 1]] ? segtree[pos << 1] : segtree[pos << 1 | 1];
        segtree[pos] == next ? (pos = 1) : (segtree[pos] = next);
    }
}
ul query(ul l, ul r, const li w[])
{
    ul ret = 0;
    for (l = l - 1 | segsz, r = r + 1 | segsz; l ^ r ^ 1; l >>= 1, r >>= 1) {
        if (~l & 1) {
            ret = w[ret] < w[segtree[l ^ 1]] ? ret : segtree[l ^ 1];
        }
        if (r & 1) {
            ret = w[ret] < w[segtree[r ^ 1]] ? ret : segtree[r ^ 1];
        }
    }
    return ret;
}
li len(ul a, ul b, const vec p[])
{
    if (!a || !b) {
        return std::max(p[a ^ b].x, p[a ^ b].y) - std::min(p[a ^ b].x, p[a ^ b].y);
    } else {
        return norm(p[a] - p[b]);
    }
}
void mintreel1(const vec p[], std::vector<ul> edge[], ul m)
{
    static ul o[maxm + 1];
    static std::vector<std::pair<ul, ul>> edges;
    static li dir3p[maxm + 1];
    static li dir1p[maxm + 1];
    edges.resize(0);
    for (ul i = 0; i <= m; ++i) {
        edge[i].resize(0);
        fa[i] = i;
        rk[i] = 0;
        o[i] = i;
        edges.push_back(std::pair<ul, ul>(0, i));
    }
    static const std::vector<vec> dirs = {vec(1, 0), vec(0, 1)};
    for (const auto& dir1 : dirs) {
        for (li lambda : {-1, 1}) {
            const vec dirt = vec(dir1.y, dir1.x) * lambda;
            const vec dir2 = vec(0, 0) - dirt - dir1;
            const vec dir3 = dirt - dir1;
            for (ul i = 1; i <= m; ++i) {
                dir3p[i] = dir3 * p[i];
                dir1p[i] = dir1 * p[i];
            }
            std::sort(o + 1, o + m + 1, [&](ul a, ul b){return dir1p[a] != dir1p[b] ? dir1p[a] < dir1p[b] : (dir3p[a] != dir3p[b] ? dir3p[a] > dir3p[b] : a < b);});
            dir3p[0] = dir3 * li(maxn + 1) * dir3;
            std::memset(segtree, 0, sizeof(segtree));
            li mn = 1e9;
            for (const auto& v : {vec(1, 1), vec(maxn, maxn), vec(1, maxn)}) {
                mn = std::min(mn, v * dir2);
            }
            for (ul i = 1; i <= m; ++i) {
                auto t = query(1, p[o[i]] * dir2 - mn + 1, dir3p);
                if (t) {
                    edges.push_back(std::pair<ul, ul>(o[i], t));
                }
                change(p[o[i]] * dir2 - mn + 1, o[i], dir3p);
            }
        }
    }
    std::sort(edges.begin(), edges.end(), [&](const std::pair<ul, ul>& a, const std::pair<ul, ul>& b){
            return len(a.first, a.second, p) < len(b.first, b.second, p);});
    for (const auto& e : edges) {
        ul a = e.first;
        ul b = e.second;
        if (connect(a, b)) {
            edge[a].push_back(b);
            edge[b].push_back(a);
        }
    }
}
std::deque<ul> queue;
int main()
{
    std::scanf("%u", &T);
    for (ul Case = 1; Case <= T; ++Case) {
        auto start = std::clock();
        std::scanf("%u%u", &n, &m);
        for (ul i = 1; i <= n; ++i) {
            edge[i].resize(0);
        }
        for (ul i = 1; i <= n - 1; ++i) {
            ul u, v, d;
            std::scanf("%u%u%u", &u, &v, &d);
            edge[u].push_back(edge_t(v, d));
            edge[v].push_back(edge_t(u, d));
        }
        ul root = 1;
        depth[root] = 0;
        p[root] = 0;
        search1(root);
        tim = 0;
        hvhd[root] = root;
        hvlen[root] = 1;
        search2(root);
        for (ul i = 1; i <= n; ++i) {
            if (hvhd[i] == i) {
                hvb[i] = std::round(std::sqrt(hvlen[i]));
                hvbdfn[rdfn[i]] = hvb[i];
            }
        }
        for (ul r = 1; r <= n; ++r) {
            ul rh = rdfnhvhddfn[r];
            ul b = hvbdfn[rh];
            ul q = (r - rh) / b;
            alpha[r] = rh + q * b;
        }
        for (ul i = 1; i <= m; ++i) {
            std::scanf("%u%u", &qs[i].l, &qs[i].r);
            qs[i].val = 0;
        }
        for (ul i = 1; i <= m; ++i) {
            querypoint[i] = vec(qs[i].l, qs[i].r);
        }
        mintreel1(querypoint, mintree, m);
        while (queue.size()) {
            queue.pop_front();
        }
        for (ul i = 0; i <= n; ++i) {
            cs[i].resize(0);
        }
        for (ul start : mintree[0]) {
            queue.push_back(start);
            fa[start] = 0;
            cs[qs[start].l - 1].push_back(std::pair<li, std::pair<ul, ul>>(start, std::pair<ul, ul>(qs[start].l + 1, qs[start].r)));
        }
        while (queue.size()) {
            ul curr = queue.front();
            queue.pop_front();
            for (ul next : mintree[curr]) {
                if (next == fa[curr]) {
                    continue;
                }
                queue.push_back(next);
                fa[next] = curr;
                cs[qs[next].l - 1].push_back(std::pair<li, std::pair<ul, ul>>(next, std::pair<ul, ul>(qs[curr].r + 1, qs[next].r)));
            }
        }
        init(n);
        for (ul i = 0; i <= n; ++i) {
            if (i >= 1) {
                insert(i);
            }
            sum[i] = i == 0 ? ul(0) : query(i);
            if (i >= 1) {
                sum[i] += sum[i - 1];
            }
            for (const auto& p : cs[i]) {
                ul to = p.first;
                ul a = p.second.first, b = p.second.second;
                if (a <= b) {
                    for (ul i = a; i <= b; ++i) {
                        qs[to].val -= query(i);
                    }
                } else {
                    for (ul i = b + 1; i <= a - 1; ++i) {
                        qs[to].val += query(i);
                    }
                }
            }
        }
        for (li it = 1; it <= m; ++it) {
            qs[it].val += fa[it] ? sum[qs[it].r] - sum[qs[fa[it]].r] : sum[qs[it].r] - sum[qs[it].l];
        }
        while (queue.size()) {
            queue.pop_front();
        }
        for (ul i = 0; i <= n; ++i) {
            cs[i].resize(0);
        }
        for (ul start : mintree[0]) {
            queue.push_back(start);
            fa[start] = 0;
            cs[qs[start].l + 1].push_back(std::pair<li, std::pair<ul, ul>>(start, std::pair<ul, ul>(qs[start].l, qs[start].l - 1)));
        }
        while (queue.size()) {
            ul curr = queue.front();
            queue.pop_front();
            for (ul next : mintree[curr]) {
                if (next == fa[curr]) {
                    continue;
                }
                queue.push_back(next);
                fa[next] = curr;
                cs[qs[curr].r + 1].push_back(std::pair<li, std::pair<ul, ul>>(next, std::pair<ul, ul>(qs[curr].l, qs[next].l - 1)));
            }
        }
        init(n);
        for (ul i = n + 1; i >= 1; --i) {
            if (i <= n) {
                insert(i);
            }
            sum[i] = i == n + 1 ? ul(0) : query(i);
            if (i <= n) {
                sum[i] += sum[i + 1];
            }
            for (const auto& p : cs[i]) {
                ul to = p.first;
                ul a = p.second.first, b = p.second.second;
                if (a <= b) {
                    for (ul i = a; i <= b; ++i) {
                        qs[to].val += query(i);
                    }
                } else {
                    for (ul i = b + 1; i <= a - 1; ++i) {
                        qs[to].val -= query(i);
                    }
                }
            }
        }
        for (li it = 1; it <= m; ++it) {
            qs[it].val -= fa[it] ? sum[qs[fa[it]].l] - sum[qs[it].l] : sum[qs[it].l] - sum[qs[it].l];
        }
        while (queue.size()) {
            queue.pop_front();
        }
        for (ul start : mintree[0]) {
            queue.push_back(start);
            fa[start] = 0;
        }
        while (queue.size()) {
            ul curr = queue.front();
            queue.pop_front();
            qs[curr].val += qs[fa[curr]].val;
            for (ul next : mintree[curr]) {
                if (fa[curr] == next) {
                    continue;
                }
                queue.push_back(next);
                fa[next] = curr;
            }
        }
        for (ul i = 1; i <= m; ++i) {
            std::printf("%u\n", qs[i].val);
        }
    }
    return 0;
}

I、Yajilin 6875

插头动归，为了思考方便，没有选择一格一格更新，而是一行一行更行，这样会慢一些，但勉强能过。

#include <bits/stdc++.h>
using ul = std::uint32_t;
using li = std::int32_t;
using ull = std::uint64_t;
using ll = std::int64_t;
const ul maxcntfrom = 31189;
enum entry {
    x,
    tr,
    tl,
    br,
    bl,
    lr,
    tb
};
enum dir {
    t,
    b,
    l,
    r
};
bool right(entry y)
{
    return y == tr || y == lr || y == br;
}
bool left(entry y)
{
    return y == tl || y == lr || y == bl;
}
bool top(entry y)
{
    return y == tl || y == tr || y == tb;
}
bool buttom(entry y)
{
    return y == bl || y == br || y == tb;
}
const ul maxn = 10;
ul brackstack[maxn + 1];
ul match[maxn + 1];
char from[maxn + 1];
entry edge[maxn + 1];
char to[maxn + 1];
bool alvis[maxn + 1];
ul cnt[2];
ul go1(ul i)
{
    dir prev = b;
    while (true) {
        alvis[i] = true;
        if (prev == b) {
            if (edge[i] == bl) {
                prev = r;
                --i;
            } else if (edge[i] == br) {
                prev = l;
                ++i;
            } else if (edge[i] == tb) {
                prev = t;
                i = match[i];
            }
        } else if (prev == t) {
            if (edge[i] == tl) {
                prev = r;
                --i;
            } else if (edge[i] == tr) {
                prev = l;
                ++i;
            } else if (edge[i] == tb) {
                break;
            }
        } else if (prev == l) {
            if (edge[i] == lr) {
                prev = l;
                ++i;
            } else if (edge[i] == tl) {
                prev = t;
                i = match[i];
            } else if (edge[i] == bl) {
                break;
            }
        } else if (prev == r) {
            if (edge[i] == lr) {
                prev = r;
                --i;
            } else if (edge[i] == tr) {
                prev = t;
                i = match[i];
            } else if (edge[i] == br) {
                break;
            }
        }
    }
    return i;
}
void go2(ul i)
{
    dir prev = r;
    while (!alvis[i]) {
        alvis[i] = true;
        if (prev == t) {
            if (edge[i] == tl) {
                prev = r;
                --i;
            } else if (edge[i] == tr) {
                prev = l;
                ++i;
            }
        } else if (prev == l) {
            if (edge[i] == lr) {
                prev = l;
                ++i;
            } else if (edge[i] == tl) {
                prev = t;
                i = match[i];
            }
        } else if (prev == r) {
            if (edge[i] == lr) {
                prev = r;
                --i;
            } else if (edge[i] == tr) {
                prev = t;
                i = match[i];
            }
        }
    }
}
ul fromid[1 << 20];
ul gethash(char str[], ul n)
{
    ul ret = 0;
    for (ul i = 1; i <= n; ++i) {
        ret *= 4;
        if (str[i] == '1') {
            ret += 1;
        }
        if (str[i] == '(') {
            ret += 2;
        }
        if (str[i] == ')') {
            ret += 3;
        }
    }
    return ret;
}
ul space[ul(1e7)];
ul* currend = space;
class trans_t {
public:
    ul* begin;
    ul* end;
    ul toid;
};
std::vector<trans_t> trans[maxn + 1][maxcntfrom + 1][2];
ul cntfrom[maxn + 1];
std::vector<ul> ablein[maxn + 1];
std::vector<ul> ableout[maxn + 1];
bool possible[maxn + 1][maxn + 1][maxcntfrom + 1][2];
bool possible2[maxn + 1][maxn + 1][maxcntfrom + 1][2];
std::vector<ul> pv[maxn + 1][maxn + 1][2];
trans_t fromastrans[maxn + 1][maxcntfrom + 1];
void search1(ul pos, ul n)
{
    if (pos == n + 1) {
        ul addcircle = 0;
        for (ul i = 1; i <= n; ++i) {
            to[i] = edge[i] == x ? '1' : '0';
            alvis[i] = false;
        }
        for (ul i = 1; i <= n; ++i) {
            if (buttom(edge[i]) && !alvis[i]) {
                to[i] = '(';
                to[go1(i)] = ')';
            }
        }
        for (ul i = 1; i <= n; ++i) {
            if (edge[i] == tr && !alvis[i]) {
                if (addcircle) {
                    return;
                }
                go2(i);
                ++addcircle;
            }
        }
        trans_t tmp;
        tmp.toid = fromid[gethash(to, n)];
        tmp.begin = currend;
        for (ul i = 1; i <= n; ++i) {
            if (edge[i] == x) {
                *currend = i;
                ++currend;
            }
        }
        tmp.end = currend;
        trans[n][cntfrom[n]][addcircle].push_back(tmp);
        ++cnt[addcircle];
        return;
    }
    for (entry curr : {x, tr, tl, br, bl, lr, tb}) {
        edge[pos] = curr;
        if (right(edge[pos - 1]) != left(curr)) {
            continue;
        }
        if (left(curr) && pos == 1) {
            continue;
        }
        if (right(curr) && pos == n) {
            continue;
        }
        if (top(curr) == (from[pos] == '0' || from[pos] == '1')) {
            continue;
        }
        if (curr == x && from[pos] == '1') {
            continue;
        }
        if (pos != 1 && curr == x && edge[pos - 1] == x) {
            continue;
        }
        search1(pos + 1, n);
    }
}
void search2(ul pos, ul stacksize, ul n)
{
    if (stacksize > n - pos + 1) {
        return;
    }
    if (pos == n + 1) {
        ul sz = 0;
        bool flag = true;
        for (ul i = 1; i <= n; ++i) {
            if (from[i] == '0' && sz == 0) {
                flag = false;
            }
            if (from[i] == '1' && sz == 1) {
                flag = false;
            }
            if (from[i] == '(') {
                ++sz;
                if (sz == 2) {
                    flag = false;
                }
                brackstack[sz] = i;
            } else if (from[i] == ')') {
                match[i] = brackstack[sz];
                match[brackstack[sz]] = i;
                --sz;
            }
        }
        ++cntfrom[n];
        if (flag) {
            ablein[n].push_back(cntfrom[n]);
        }
        fromastrans[n][cntfrom[n]].begin = currend;
        for (ul i = 1; i <= n; ++i) {
            if (from[i] == '1') {
                *currend = i;
                ++currend;
            }
        }
        fromastrans[n][cntfrom[n]].end = currend;
        search1(1, n);
        return;
    }
    from[pos] = '0';
    search2(pos + 1, stacksize, n);
    if (from[pos - 1] != '1') {
        from[pos] = '1';
        search2(pos + 1, stacksize, n);
    }
    if (stacksize > 0) {
        from[pos] = ')';
        search2(pos + 1, stacksize - 1, n);
    }
    from[pos] = '(';
    search2(pos + 1, stacksize + 1, n);
}
void search3(ul pos, ul stacksize, ul n)
{
    if (stacksize > n - pos + 1) {
        return;
    }
    if (pos == n + 1) {
        ++cntfrom[n];
        fromid[gethash(from, n)] = cntfrom[n];
        bool flag = true;
        for (ul i = 1; i <= n; ++i) {
            if (from[i] == '(' || from[i] == ')') {
                flag = false;
                break;
            }
        }
        if (flag) {
            ableout[n].push_back(cntfrom[n]);
        }
        return;
    }
    from[pos] = '0';
    search3(pos + 1, stacksize, n);
    if (from[pos - 1] != '1') {
        from[pos] = '1';
        search3(pos + 1, stacksize, n);
    }
    if (stacksize > 0) {
        from[pos] = ')';
        search3(pos + 1, stacksize - 1, n);
    }
    from[pos] = '(';
    search3(pos + 1, stacksize + 1, n);
}
ul ans[maxn + 1][maxcntfrom + 1][2];
ul T;
ul n;
const ul inf = ~ul(0);
ul cost[maxn + 1];
char outstr[100000];
char* outend = outstr;
int main()
{
    for (ul n = 2; n <= maxn; ++n) {
        search3(1, 0, n);
        cntfrom[n] = 0;
        cnt[0] = cnt[1] = 0;
        search2(1, 0, n);
        for (ul to : ableout[n]) {
            possible[n][n][to][1] = true;
        }
        for (ul i = n - 1; i >= 1; --i) {
            for (ul from = 1; from <= cntfrom[n]; ++from) {
                for (const auto& edge : trans[n][from][0]) {
                    ul to = edge.toid;
                    if (possible[n][i + 1][to][0]) {
                        possible[n][i][from][0] = true;
                        break;
                    }
                }
                if (!possible[n][i][from][0]) {
                    for (const auto& edge : trans[n][from][1]) {
                        ul to = edge.toid;
                        if (possible[n][i + 1][to][1]) {
                            possible[n][i][from][0] = true;
                            break;
                        }
                    }
                }
                for (const auto& edge : trans[n][from][0]) {
                    ul to = edge.toid;
                    if (possible[n][i + 1][to][1]) {
                        possible[n][i][from][1] = true;
                        break;
                    }
                }
            }
        }
        for (ul from : ablein[n]) {
            if (possible[n][1][from][0]) {
                possible2[n][1][from][0] = true;
            }
        }
        for (ul i = 2; i <= n; ++i) {
            for (ul from = 1; from <= cntfrom[n]; ++from) {
                if (possible2[n][i - 1][from][0]) {
                    for (const auto& edge : trans[n][from][0]) {
                        ul to = edge.toid;
                        if (possible[n][i][to][0]) {
                            possible2[n][i][to][0] = true;
                        }
                    }
                    for (const auto& edge : trans[n][from][1]) {
                        ul to = edge.toid;
                        if (possible[n][i][to][1]) {
                            possible2[n][i][to][1] = true;
                        }
                    }
                }
                if (possible2[n][i - 1][from][1]) {
                    for (const auto& edge : trans[n][from][0]) {
                        ul to = edge.toid;
                        if (possible[n][i][to][1]) {
                            possible2[n][i][to][1] = true;
                        }
                    }
                }
            }
        }
        for (ul i = 1; i <= n; ++i) {
            for (ul id = 1; id <= cntfrom[n]; ++id) {
                for (ul plus = 0; plus <= 1; ++plus) {
                    if (possible2[n][i][id][plus]) {
                        pv[n][i][plus].push_back(id);
                    }
                }
            }
        }
    }
    std::scanf("%u", &T);
    for (ul Case = 1; Case <= T; ++Case) {
        std::scanf("%u", &n);
        for (ul from = 1; from <= cntfrom[n]; ++from) {
            ans[1][from][0] = ans[1][from][1] = inf;
        }
        for (ul j = 1; j <= n; ++j) {
            std::scanf("%u", &cost[j]);
        }
        for (ul from : pv[n][1][0]) {
            ans[1][from][0] = 0;
            for (ul* j = fromastrans[n][from].begin; j != fromastrans[n][from].end; ++j) {
                ans[1][from][0] += cost[*j];
            }
        }
        for (ul i = 2; i <= n; ++i) {
            for (ul j = 1; j <= n; ++j) {
                std::scanf("%u", &cost[j]);
            }
            for (ul to = 1; to <= cntfrom[n]; ++to) {
                ans[i][to][0] = ans[i][to][1] = inf;
            }
            for (ul from : pv[n][i - 1][0]) {
                if (ans[i - 1][from][0] != inf) {
                    for (const auto& edge : trans[n][from][0]) {
                        ul newcost = ans[i - 1][from][0];
                        ul to = edge.toid;
                        if (!possible[n][i][to][0]) {
                            continue;
                        }
                        for (ul* j = edge.begin; j != edge.end; ++j) {
                            newcost += cost[*j];
                        }
                        if (ans[i][to][0] == inf || ans[i][to][0] < newcost) {
                            ans[i][to][0] = newcost;
                        }
                    }
                    for (const auto& edge : trans[n][from][1]) {
                        ul newcost = ans[i - 1][from][0];
                        ul to = edge.toid;
                        if (!possible[n][i][to][1]) {
                            continue;
                        }
                        for (ul* j = edge.begin; j != edge.end; ++j) {
                            newcost += cost[*j];
                        }
                        if (ans[i][to][1] == inf || ans[i][to][1] < newcost) {
                            ans[i][to][1] = newcost;
                        }
                    }
                }
            }
            for (ul from : pv[n][i - 1][1]) {
                if (ans[i - 1][from][1] != inf) {
                    for (const auto& edge : trans[n][from][0]) {
                        ul newcost = ans[i - 1][from][1];
                        ul to = edge.toid;
                        if (!possible[n][i][to][1]) {
                            continue;
                        }
                        for (ul* j = edge.begin; j != edge.end; ++j) {
                            newcost += cost[*j];
                        }
                        if (ans[i][to][1] == inf || ans[i][to][1] < newcost) {
                            ans[i][to][1] = newcost;
                        }
                    }
                }
            }
        }
        ul out = 0;
        for (ul to : ableout[n]) {
            if (ans[n][to][1] != inf) {
                out = std::max(out, ans[n][to][1]);
            }
        }
        std::sprintf(outend, "%u\n", out);
        outend += std::strlen(outend);
    }
    std::printf(outstr);
    return 0;
}

J、Jump 6876

官方题解写得很清楚，如下：

其中“区间加减、区间求最大最小值”可以依靠差分实现非递归。（根存的是全局最大值，其他节点存的是“此区间的最大值减去母区间的最大值得到的差”）

#include <bits/stdc++.h>
using ul = std::uint32_t;
using li = std::int32_t;
using ull = std::uint64_t;
using ll = std::int64_t;
using lf = double;
const ul maxn = 2e5;
const ul maxm = 2e5;
ul T;
ul n, m, rt;
class edge_t {
public:
    ul to = 0;
    ull len = 0;
    edge_t()=default;
    edge_t(ul a, ull b): to(a), len(b) {}
};
std::vector<edge_t> edge[maxn + 1];
ul fa[maxn + 1];
ull dep[maxn + 1];
ul len[maxn + 1];
ul lencnt[maxn + 1];
void search(ul curr)
{
    len[curr] = 0;
    for (const edge_t& e : edge[curr]) {
        ul next = e.to;
        if (next == fa[curr]) {
            continue;
        }
        fa[next] = curr;
        dep[next] = dep[curr] + e.len;
        search(next);
        len[curr] = std::max(len[curr], len[next] + ul(1));
    }
    ++lencnt[len[curr]];
}
ul B1, B2;
ul type[maxn + 1];
ul a[maxn + 1];
std::list<std::pair<ul, ul>> list[maxn + 1];
ull mindep[maxn + 1];
ull lentodep[512][maxn + 1];
const ul sz = 1 << 18;
li tree[512][sz << 1];
void change(ul l, ul r, li val, li tree[])
{
    li tmp;
    for (l = l - 1 | sz, r = r + 1 | sz; l ^ r ^ 1; l >>= 1, r >>= 1) {
        if (~l & 1) {
            tree[l ^ 1] += val;
        }
        if (r & 1) {
            tree[r ^ 1] += val;
        }
        tmp = std::max(tree[l], tree[l ^ 1]);
        tree[l] -= tmp;
        tree[l ^ 1] -= tmp;
        tree[l >> 1] += tmp;
        tmp = std::max(tree[r], tree[r ^ 1]);
        tree[r] -= tmp;
        tree[r ^ 1] -= tmp;
        tree[r >> 1] += tmp;
    }
    for (ul i = l; i >> 1; i >>= 1) {
        tmp = std::max(tree[i], tree[i ^ 1]);
        tree[i] -= tmp;
        tree[i ^ 1] -= tmp;
        tree[i >> 1] += tmp;
    }
}
li query(ul l, ul r, const li tree[])
{
    li lans = -1e7;
    li rans = -1e7;
    for (l = l - 1 | sz, r = r + 1 | sz; l ^ r ^ 1; l >>= 1, r >>= 1) {
        if (~l & 1) {
            lans = std::max(lans, tree[l ^ 1]);
        }
        if (r & 1) {
            rans = std::max(rans, tree[r ^ 1]);
        }
        lans += tree[l >> 1];
        rans += tree[r >> 1];
    }
    li ans = std::max(lans, rans);
    for (ul i = l; i >> 1; i >>= 1) {
        ans += tree[i >> 1];
    }
    return ans;
}
int main()
{
    std::scanf("%u", &T);
    for (ul Case = 1; Case <= T; ++Case) {
        std::scanf("%u%u%u", &n, &m, &rt);
        for (ul i = 1; i <= n; ++i) {
            type[i] = 0;
            edge[i].resize(0);
            lencnt[i] = 0;
        }
        lencnt[0] = 0;
        for (ul i = 1; i <= n - 1; ++i) {
            ul u, v, d;
            std::scanf("%u%u%u", &u, &v, &d);
            edge[u].push_back(edge_t(v, d));
            edge[v].push_back(edge_t(u, d));
        }
        fa[rt] = rt;
        dep[rt] = 0;
        search(rt);
        B1 = 0;
        for (ul i = 1; i <= n; ++i) {
            if ((lf(n) + lf(m * std::log(n) / std::log(2))) * lencnt[i] + lf(n) * i < (lf(n) + lf(m * std::log(n) / std::log(2))) * lencnt[B1] + lf(n) * B1) {
                B1 = i;
            }
        }
        B2 = std::round(std::sqrt(n));
        ul cnt = 0;
        for (ul i = 1; i <= n; ++i) {
            mindep[i / B2] = 1e18;
            list[i / B2].clear();
            if (len[i] == B1) {
                ++cnt;
                std::memset(tree[cnt], 0, sizeof(li) * (sz << 1));
                tree[cnt][1] = -li(m);
                for (ul j = i; ; j = fa[j]) {
                    type[j] = cnt;
                    if (type[fa[j]] || len[fa[j]] != len[j] + 1) {
                       break;
                    }      
                }
                for (ul t = B1 - 1; t != B1; ++t) {
                    lentodep[cnt][t] = 1e18;
                }
                for (ul j = i, t = B1; t <= n; j = fa[j], ++t) {
                    lentodep[cnt][t] = dep[j];
                }
            }
        }
        for (ul i = 1; i <= n; ++i) {
            std::scanf("%u", &a[i]);
            if (len[a[i]] < B1) {
                list[i / B2].push_back(std::pair<ul, ul>(i, a[i]));
                mindep[i / B2] = std::min(mindep[i / B2], dep[a[i]]);
            } else {
                change(i, i, len[a[i]] + li(m), tree[type[a[i]]]);
            }
        }
        for (ul i = 1; i <= m; ++i) {
            ul qt, l, r;
            std::scanf("%u%u%u", &qt, &l, &r);
            if (qt == 1) {
                for (ul i = 1; i <= cnt; ++i) {
                    change(l, r, 1, tree[i]);
                }
                ul s = l / B2;
                ul t = r / B2;
                for (ul i = s; i <= t; ++i) {
                    for (auto it = list[i].begin(); it != list[i].end(); ) {
                        if (it->first < l || it->first > r) {
                            ++it;
                            continue;
                        }
                        it->second = fa[it->second];
                        if (len[it->second] >= B1) {
                            change(it->first, it->first, li(len[it->second]) - query(it->first, it->first, tree[type[it->second]]), tree[type[it->second]]);
                            it = list[i].erase(it);
                        } else {
                            mindep[i] = std::min(mindep[i], dep[it->second]);
                            ++it;
                        }
                    }
                }
            } else {
                ull ans = 1e18;
                for (ul i = 1; i <= cnt; ++i) {
                    ans = std::min(ans, lentodep[i][std::max(std::min(query(l, r, tree[i]), li(n)), li(B1 - 1))]);
                }
                ul s = l / B2;
                ul t = r / B2;
                for (const auto& p : list[s]) {
                    if (p.first < l || p.first > r) {
                        continue;
                    }
                    ans = std::min(ans, dep[p.second]);
                }
                for (const auto& p : list[t]) {
                    if (p.first < l || p.first > r) {
                        continue;
                    }
                    ans = std::min(ans, dep[p.second]);
                }
                for (ul i = s + 1; i < t; ++i) {
                    ans = std::min(ans, mindep[i]);
                }
                std::printf("%llu\n", ans);
            }
        }
    }
    return 0;
}