LNOI2014 LCA

首先询问显然是可以差分的。

然后考虑如何计算点$vtx$与点$z$的LCA的深度。

让点$vtx$到树根的所有点的点权$+1$,然后查询$z$到树根的点权和，这个值就是$z$与$vtx$的LCA的深度。

然后把每个询问拆成两个前缀和，然后按照询问端点排序，一个一个处理。

处理点$vtx$的询问时，先把$vtx$到根的所有点权值+1，然后对于所有的$z$,查询$z$到树根的权值和即可。

#include <assert.h>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t mod = 201314;
const int_t LARGE = 2e5;
const int_t INF = 0x7fffffff;
std::ostream& operator<<(std::ostream& os, const struct Node& node);
struct Node {
    Node*& left;
    Node*& right;
    Node* chds[2] = {nullptr, nullptr};
    Node* parent = nullptr;
    int_t id;
    int_t value;
    int_t sum;
    int_t max;
    int_t mark = 0;
    int_t size = 1;
    bool flipped = false;
    Node(int_t val) : left(chds[0]), right(chds[1]) {
        this->value = this->sum = this->max = val;
        // this->max = -INF;
    }
    void flip() {
        this->flipped ^= 1;
        std::swap(left, right);
    }
    void add(int_t x) {
        this->mark += x;
        this->sum += size * x;
        this->max += x;
        value += x;
    }
    void pushDown() {
        if (left) {
            left->add(mark);
            if (flipped) left->flip();
        }
        if (right) {
            right->add(mark);
            if (flipped) right->flip();
        }
        flipped = false;
        mark = 0;
    }
    void updateFrom(Node* node) {
        size += node->size;
        sum += node->sum;
        max = std::max(max, node->max);
        node->parent = this;
    }
    void maintain() {
        max = sum = value;
        size = 1;
        if (left) updateFrom(left);
        if (right) updateFrom(right);
    }
    int_t chdOf() const {
        if (parent == nullptr) return -1;
        if (this == parent->left)
            return 0;
        else if (this == parent->right)
            return 1;
        else
            return -1;
    }
};
Node* nodes[LARGE + 1];
int n, q;
// node 围绕父节点旋转
void rotate(Node* node) {
    Node* Pr = node->parent;
    Pr->pushDown();
    node->pushDown();
    int_t side = node->chdOf();
    int_t sidep = Pr->chdOf();
    assert(side != -1);
    Node* Gr = Pr->parent;
    Pr->chds[side] = node->chds[side ^ 1];
    node->chds[side ^ 1] = Pr;
    node->parent = Gr;
    Pr->maintain();
    node->maintain();
    if (sidep != -1 && Gr) {
        Gr->chds[sidep] = node;
        Gr->maintain();
    }
}
//判断node是否是辅助树的根
bool isAuxRoot(Node* node) {
    if (node == nullptr || node->parent == nullptr) return true;
    return node->chdOf() == -1;
}
void splay(Node* node) {
    static Node* stack[LARGE];
    int_t top = 0;
    Node* curr = node;
    while (true) {
        stack[top++] = curr;
        if (isAuxRoot(curr)) break;
        curr = curr->parent;
    }
    while (top) {
        stack[--top]->pushDown();
    }

    while (isAuxRoot(node) == false) {
        if (isAuxRoot(node->parent)) {
            rotate(node);
        } else {
            int_t p1 = node->chdOf();
            int_t p2 = node->chdOf();
            if (p1 == p2) {
                rotate(node->parent);
            } else {
                rotate(node);
            }
            rotate(node);
        }
    }
}

void access(Node* node) {
    Node* last = nullptr;
    while (node) {
        splay(node);
        node->right = last;
        last = node;
        node->maintain();
        node = node->parent;
    }
}

void changeRoot(Node* node) {
    access(node);
    splay(node);
    node->flip();
}

int_t query(Node* v1, Node* v2) {
    changeRoot(v1);
    access(v2);
    splay(v2);
    return v2->sum;
}
void add(Node* v1, Node* v2, int_t val) {
    changeRoot(v1);
    access(v2);
    splay(v2);
    v2->add(val);
}

void link(Node* v1, Node* v2) {
    //连边一定一定要换根！！
    changeRoot(v2);
    access(v1);
    splay(v1);
    v1->pushDown();
    v1->right = v2;
    v1->maintain();
}

int main() {
    // freopen("qwq.txt", "r", stdin);
    static int_t result[LARGE + 1];
    struct Operation {
        int_t ID;
        int_t type;
        int_t z;
    };
    std::vector<Operation> querys[LARGE + 1];
    scanf("%d%d", &n, &q);
    for (int_t i = 1; i <= n; i++) {
        nodes[i] = new Node(0);
        nodes[i]->id = i;
    }
    for (int_t i = 2; i <= n; i++) {
        int_t parent;
        scanf("%lld", &parent);
        parent += 1;
        link(nodes[i], nodes[parent]);
    }
    for (int_t i = 1; i <= q; i++) {
        int_t left, right, z;
        scanf("%lld%lld%lld", &left, &right, &z);
        z++;
        left++;
        right++;
        querys[left - 1].push_back(Operation{i, -1, z});
        querys[right].push_back(Operation{i, 1, z});
    }
    for (int_t i = 1; i <= n; i++) {
        //路径上的点权+1
        add(nodes[1], nodes[i], 1);
        //处理这个端点的答案
        for (const auto& opt : querys[i]) {
            int_t x = opt.type * query(nodes[1], nodes[opt.z]);
            result[opt.ID] += x;
        }
    }
    for (int_t i = 1; i <= q; i++) {
        printf("%lld\n", result[i] % mod);
    }
    return 0;
}