题目描述

给定一棵大小为 的树，每一个点上有一个物品，物品的属性 。

有 次操作，操作分两类，修改和询问。

  • 修改给定 , ，表示点 新增了一个属性为 的物品。

  • 询问给定 , , ，询问距离节点 最近的一个 "带有属性的物品" 的节点（下面称这种节点为关键节点）。

正解

如果是随机树的话，那么有一个小 trick，在两个点的 lca 计算贡献。

每一个点 维护一个动态开点的线段树，区间 维护的是距离点 最近的关键节点。

修改每一个点的时候暴力往上跳父亲（树高为 ），然后在祖先修改线段树。

查询的时候同样是暴力往上跳父亲，在祖先查询最近的关键节点。

复杂度为 。

现在考虑树不随机怎么做，常见套路是动态点分治。

先建出点分树，预处理每个分治中心到子节点的距离。

修改暴力往上跳，在点分树上的祖先修改。

查询类似，也是暴力往上跳就行。

复杂度同为 。

note

需要注意到的是，如果写动态开点线段树的话，空间复杂度是 。 （大概几个 G 吧）

于是我写的是平衡树 Splay，空间复杂度 。

你们猜猜看我的代码有多长？

#include <bits/stdc++.h>
#define N 100005
#define inf 1000000005

using namespace std;

int n, m;
int arr[N];
int head[N], nex[N << 1], to[N << 1], eVal[N << 1], ecnt;

inline int read() {
    int x = 0;
    char ch = getchar();
    while (!isdigit(ch))
        ch = getchar();
    while (isdigit(ch))
        x = x * 10 + ch - '0', ch = getchar();
    return x;
}
inline void addE(int u, int v, int w) {
    to[++ecnt] = v, eVal[ecnt] = w;
    nex[ecnt] = head[u], head[u] = ecnt;
}

void preDfs(int u, int fa) {
    for (int i = head[u], v; i; i = nex[i]) {
        v = to[i];
        if (v == fa)
            continue;
        preDfs(v, u);
    }
}

int totSi***Size, curRoot;
int fa[N], siz[N], dep[N], dis[30][N];

void getDist(int u, int fa) { // get size by the way
    siz[u] = 1;
    for (int i = head[u], v; i; i = nex[i]) {
        v = to[i];
        if (v == fa || ::fa[v])
            continue;
        dis[dep[curRoot]][v] = dis[dep[curRoot]][u] + eVal[i];
        getDist(v, u);
        siz[u] += siz[v];
    }
}
void getRoot(int u, int fa) {
    int maxSize = 0;
    for (int i = head[u], v; i; i = nex[i]) {
        v = to[i];
        if (v == fa || ::fa[v])
            continue;
        getRoot(v, u);
        if (siz[v] > maxSize)
            maxSize = siz[v];
    }
    maxSize = max(maxSize, totSize - siz[u]);
    if (maxSi***Si***Size = maxSize, curRoot = u;
}
void poiDiv(int u) {
    getDist(u, 0);
    for(int i = head[u], v; i; i = nex[i]) {
        v = to[i];
        if(::fa[v])
            continue;
        minSize = n;
        totSize = siz[v];
        getRoot(v, u);
        fa[curRoot] = u, dep[curRoot] = dep[u] + 1;
        poiDiv(curRoot);
    }
}

int totNode;
struct node {
    int ch[2], fa, key;
       int val, mic;
} a[N * 30];
int creNode(int key, int val) {
    int u = ++totNode;
    a[u].key = key, a[u].val = a[u].mic = val;
    return u;
}

struct BST {
#define lch(x) (a[x].ch[0])
#define rch(x) (a[x].ch[1])
#define par(x) (a[x].fa)
    int root;
    void link(int u, int f, bool ind) { par(u) = f, a[f].ch[ind] = u; }
    void update(int u) { a[u].mic = min(a[u].val, min(a[lch(u)].mic, a[rch(u)].mic)); }
    void rotate(int u) {
        int f = par(u), g = par(f);
        bool ind = (a[f].ch[1] == u);
        link(a[u].ch[!ind], f, ind), link(f, u, !ind), link(u, g, rch(g) == f);
        update(f);
    }
    void splay(int u, int tar = 0) {
        int f, g;
        while ((f = par(u)) != tar) {
            g = par(f);
            if (g != tar)
                rotate((rch(g) == f) ^ (rch(f) == u) ? u : f);
            rotate(u);
        }
        if (!tar)
            root = u;
        update(u);
    }
    void insert(int key, int val) {
        int u = root, las = 0;
        while (u && a[u].key != key)
            las = u, u = a[u].ch[key > a[u].key];
        if (!u) {
            u = creNode(key, val);
            link(u, las, a[u].key > a[las].key);
        } else {
            a[u].val = min(a[u].val, val);
        }
        splay(u);
    }
    int pre(int key) {
        int u = root, v = 0, maxKey = -1;
        while (u) {
            if (a[u].key < key) {
                if (maxKey < a[u].key)
                    v = u, maxKey = a[u].key;
                u = rch(u);
            } else {
                u = lch(u);
            }
        }
        return v;
    }
    int suc(int key) {
        int u = root, v = 0, minKey = N + 10;
        while (u) {
            if (a[u].key > key) {
                if (minKey > a[u].key)
                    v = u, minKey = a[u].key;
                u = lch(u);
            } else {
                u = rch(u);
            }
        }
        return v;
    }
    int query(int l, int r) {
        int lp = pre(l), rp = suc(r);
        splay(lp), splay(rp, lp);
        return a[lch(rp)].mic;
    }
    void init() {
        root = creNode(0, inf);
        link(creNode(N, inf), root, 1);
    }
#undef lch
#undef rch
#undef par
} Tr[N];

int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; ++i)
        arr[i] = read();
    for (int i = 1, u, v, w; i < n; ++i) {
        u = read(), v = read(), w = read();
        addE(u, v, w), addE(v, u, w);
    }

    fa[1] = 1;
    curRoot = 1;
    poiDiv(1);
    fa[1] = 0;

    a[0].val = a[0].mic = inf;
    for (int i = 1; i <= n; ++i)
        Tr[i].init();

    for(int i = 1, u; i <= n; ++i) {
        u = i;
        while(u) {
            Tr[u].insert(arr[i], dis[dep[u]][i]);
            u = fa[u];
        }
    }

    for (int i = 1, op, x, l, r; i <= m; ++i) {
        op = read(), x = read(), l = read();
        if (op == 1) {
            int u = x;
            while(u) {
                Tr[u].insert(l, dis[dep[u]][x]);
                u = fa[u];
            }
        } else {
            r = read();
            int ans = inf, u = x;
            while(u) {
                ans = min(ans, dis[dep[u]][x] + Tr[u].query(l, r));
                u = fa[u];
            }
            if (ans >= inf) ans = -1;
            if(ans != -1) ans <<= 1;
            printf("%d\n", ans);
        }
    }
    return 0;
}