我写了一个 dijkstra + 主席树维护哈希，线段树维护的是十进制高精度数，按理来说线段树只用开 $5\times 10^5$ 的长度就可以了，但是我开 $10^6$ 都过不了，开到了 $2.4\times 10^6$ 才过，这是为什么呢？

代码：

#include <iostream>
#include <queue>
#define PII pair<int, int>
#define ull unsigned long long
#define lc(x) tr[x].lson
#define rc(x) tr[x].rson

using namespace std;

const int N = 8e5, bs = 131, mod = 1e9 + 7;

int n, m, p10[N], dis[N];
bool st[N];
int rt[N], rid, idx;
ull pw[N];
vector<PII> e[N];
struct
{
    int l, r, v, val, cnt;
    int lson, rson;
    ull hsh;
} tr[N * 15];

void pushup(int u)
{
    tr[u].val = (1ll * tr[lc(u)].val * p10[tr[rc(u)].cnt] + tr[rc(u)].val) % mod;
    tr[u].cnt = tr[lc(u)].cnt + tr[rc(u)].cnt;
    tr[u].hsh = tr[lc(u)].hsh * pw[tr[rc(u)].r - tr[rc(u)].l + 1] + tr[rc(u)].hsh;
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if (l == r)
        return (void)(tr[u].hsh = tr[u].v = -1);
    int mid = l + r >> 1;
    build(lc(u) = ++idx, l, mid), build(rc(u) = ++idx, mid + 1, r), pushup(u);
}

void modify(int prv, int &u, int p, int v)
{
    if (!u || u == prv)
        tr[u = ++idx] = tr[prv];
    if (tr[u].l == tr[u].r)
        return (void)(tr[u].hsh = tr[u].val = tr[u].v = v, tr[u].cnt = 1);
    int mid = tr[u].l + tr[u].r >> 1;
    if (p <= mid)
        modify(lc(prv), lc(u), p, v);
    else
        modify(rc(prv), rc(u), p, v);
    pushup(u);
}

bool cmp(int prv, int u) // prv < u
{
    if (tr[prv].cnt ^ tr[u].cnt)
        return tr[prv].cnt < tr[u].cnt;
    if (tr[u].l == tr[u].r)
        return tr[prv].v < tr[u].v;
    if (tr[lc(prv)].hsh ^ tr[lc(u)].hsh)
        return cmp(lc(prv), lc(u));
    return cmp(rc(prv), rc(u));
}

void add(int t, int v)
{
    rid++;
    int tmp[10], c = 0, p = tr[rt[t]].cnt;
    while (v)
        tmp[++c] = v % 10, v /= 10;
    for (int i = 1; i <= c; i++)
        modify(rt[t], rt[rid], p + i, tmp[c - i + 1]);
}

struct my
{
    int t, u;
    bool operator<(const my &x) const
    {
        return cmp(rt[x.t], rt[t]);
    }
};
priority_queue<my> q;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++)
        cin >> u >> v, e[u].push_back({v, i}), e[v].push_back({u, i});
    pw[0] = p10[0] = 1;
    for (int i = 1; i < N; i++)
        pw[i] = pw[i - 1] * bs, p10[i] = 10ll * p10[i - 1] % mod;
    rid = rt[1] = 1, build(1, 1, 3 * N); // 线段树长度
    dis[1] = 1, q.push({1, 1});
    while (q.size())
    {
        int u = q.top().u;
        q.pop();
        if (st[u])
            continue;
        st[u] = 1;
        for (auto [v, id] : e[u])
            if (!st[v])
            {
                add(dis[u], id);
                if (!dis[v] || cmp(rt[rid], rt[dis[v]]))
                    dis[v] = rid, q.push({rid, v});
            }
    }
    for (int i = 2; i <= n; i++)
        cout << tr[rt[dis[i]]].val << "\n";
    return 0;
}