https://www.luogu.com.cn/record/162053244

感觉不是常数问题啊,后面几个全T飞了,但应该确实让每个点在每个块只遍历了一次吧.

或者给出用时大的数据也行,我以为一条链是极限但跑的挺快()

#include <algorithm>
#include <array>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <list>
#include <vector>
#define endl '\n'
using namespace std;
using ll = long long;
using pi2 = array<int, 2>;
using pi3 = array<int, 3>;
using pi4 = array<int, 4>;

const int N = 2e5 + 500, S = 500;
const ll inf = 1e18;
int B = 500;

int n, m, rt;
vector<pi2> G[N];
int fa[N], top[N], siz[N], son[N], dep[N], arr[N], dfn[N], dcnt;
ll wdep[N];
void dfs1(int u, int f) {
    fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1;
    for (pi2 e : G[u])
        if (e[0] != f)
            wdep[e[0]] = wdep[u] + e[1], dfs1(e[0], u), siz[u] += siz[e[0]], son[u] = siz[e[0]] > siz[son[u]] ? e[0] : son[u];
}
void dfs2(int u, int tp) {
    top[u] = tp, dfn[u] = ++dcnt, arr[dfn[u]] = u;
    if (son[u])
        dfs2(son[u], tp);
    for (pi2 e : G[u])
        if (e[0] != fa[u] && e[0] != son[u])
            dfs2(e[0], e[0]);
}
int inline const jump(int u, int d) {
    d = max(d, 1);
    while (dep[top[u]] > d)
        u = fa[top[u]];
    return arr[dfn[u] - (dep[u] - d)];
}
int a[N], has_jumped[N], to_jump[S];
ll res[S];
vector<int> keys[S];
bitset<N> vis[S];
int blk[N], lft[S];
int cc = 0;
void push_tag(int b, int l, int r) {
    r = min(r, lft[b + 1] - 1), l = max(l, lft[b]);
    for (int i = l; i <= r; i++) {
        cc++;
        if (to_jump[b] != has_jumped[i]) {
            a[i] = jump(a[i], dep[a[i]] - to_jump[b] + has_jumped[i]);
            if (!vis[b][a[i]])
                vis[b][a[i]] = true, keys[b].push_back(i);
        }
        has_jumped[i] = to_jump[b];
        res[b] = min(res[b], wdep[a[i]]);
    }
    if (res[b] == 0)
        keys[b].clear();
}
ll query_part(int b, int l, int r) {
    r = min(r, lft[b + 1] - 1), l = max(l, lft[b]);
    ll ans = inf;
    for (int i = l; i <= r; i++) {
        if (to_jump[b] != has_jumped[i])
            ans = min(ans, wdep[jump(a[i], dep[a[i]] - to_jump[b] + has_jumped[i])]);
        else
            ans = min(ans, wdep[a[i]]);
    }
    return ans;
}
void tag_block(int b) {
    to_jump[b]++;
    if (res[b] == 0)
        return;
    vector<int> new_keys;
    for (int i : keys[b]) {
        if (!fa[a[i]] || vis[b][fa[a[i]]])
            continue;
        vis[b][a[i]] = true, a[i] = fa[a[i]], has_jumped[i]++, res[b] = min(res[b], wdep[a[i]]), new_keys.push_back(i);
    }
    swap(keys[b], new_keys);
}
void jump_one(int i) {
    if (!fa[a[i]])
        return;
    a[i] = fa[a[i]], vis[blk[i]][a[i]] = true, res[blk[i]] = min(res[blk[i]], wdep[a[i]]);
}
void update(int l, int r) {
    int bl = blk[l], br = blk[r];
    push_tag(bl, l, r), bl != br && (push_tag(br, l, r), 0);
    if (br - bl <= 1) {
        for (int i = l; i <= r; i++)
            jump_one(i);
        return;
    }
    for (int i = bl + 1; i < br; i++)
        tag_block(i);
    for (int i = l; i < lft[bl + 1]; i++)
        jump_one(i);
    for (int i = lft[br]; i <= r; i++)
        jump_one(i);
}
ll query(int l, int r) {
    int bl = blk[l], br = blk[r];
    ll ans = query_part(bl, l, r);
    bl != br && (ans = min(ans, query_part(br, l, r)));
    if (br - bl <= 1) {
        return ans;
    }
    for (int i = bl + 1; i < br; i++)
        ans = min(ans, res[i]);
    return ans;
}
signed main() {
//    freopen("p.in", "r", stdin);
//    freopen("a.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> rt;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }
    dfs1(rt, 0);
    dfs2(rt, rt);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        blk[i] = (i - 1) / B + 1;
    for (int i = 1; i <= blk[n] + 1; i++)
        lft[i] = min((i - 1) * B + 1, n + 1);
    for (int i = 1; i <= blk[n]; i++) {
        res[i] = inf;
        for (int j = lft[i]; j < lft[i + 1]; j++) {
            keys[i].push_back(j), vis[i][a[j]] = true;
            res[i] = min(res[i], wdep[a[j]]);
        }
    }
    for (int i = 1; i <= m; i++) {
        int opt, l, r;
        cin >> opt >> l >> r;
        if (opt == 1)
            update(l, r);
        else
            cout << query(l, r) << endl;
    }
    cerr << cc << endl;
    return 0;
}