BZOJ3626 [LNOI2014] LCA 题解（树剖+线段树）

传送门

个人感觉这题做法还是挺巧妙的。

一个点的深度，我们可以理解为从这个点到根的路径上经过了多少个点。

如果给每个点赋点权，那么求a$a$与x$x$的lca$lca$的深度，就相当于把a$a$到根的路径上每个点的点权+1$+1$，然后求x$x$到根的路径上的点权和。

点权和这个东西非常好，因为它具有区间可减性。可以把区间[l,r]$[l,r]$的答案变成[1,r]$[1,r]$的答案减去[1,l−1]$[1,l-1]$的答案，那么我们只要处理所有[1,i]$[1,i]$的答案即可。树剖+线段树可以搞定。

可以从1$1$到n$n$依次加入点，然后统计答案即可

因为是在课上做的题，写的时候比较仓促，所以有一些变量名比较随意。。。

#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
#include <vector>

template <typename T> inline void read(T& t) {
    int f = 0, c = getchar(); t = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) t = t * 10 + c - 48, c = getchar();
    if (f) t = -t;
}
#if __cplusplus >= 201103L
template <typename T, typename... Args>
inline void read(T& t, Args&... args) {
    read(t); read(args...);
}
#else
template <typename T1, typename T2>
inline void read(T1& t1, T2& t2) { read(t1); read(t2); }
template <typename T1, typename T2, typename T3>
inline void read(T1& t1, T2& t2, T3& t3) { read(t1, t2); read(t3); }
template <typename T1, typename T2, typename T3, typename T4>
inline void read(T1& t1, T2& t2, T3& t3, T4& t4) { read(t1, t2, t3); read(t4); }
template <typename T1, typename T2, typename T3, typename T4, typename T5>
inline void read(T1& t1, T2& t2, T3& t3, T4& t4, T5& t5) { read(t1, t2, t3, t4); read(t5); }
#endif  // C++11

#ifdef WIN32
#define LLIO "%I64d"
#else
#define LLIO "%lld"
#endif  // WIN32 long long
#define rep(I, A, B) for (int I = (A); I <= (B); ++I)
#define rrep(I, A, B) for (int I = (A); I >= (B); --I)
#define erep(I, X) for (int I = head[X]; I; I = next[I])

const int maxn = 5e4 + 207;
const int mod = 201314;
typedef int arrT[maxn << 1];
arrT head, dep, top, son, size, fa, dfn;
int v[maxn << 1], next[maxn << 1];
int sum[maxn << 2], delta[maxn << 2];
int n, m, index, tot;

inline void ae(int x, int y) {
    v[++tot] = y; next[tot] = head[x]; head[x] = tot;
    v[++tot] = x; next[tot] = head[y]; head[y] = tot;
}

inline void update(int x) {
    sum[x] = sum[x << 1] + sum[x << 1 | 1];
}
inline void pushdown(int curr, int l, int r) {
    if (delta[curr]) {
        int mid = (l + r) >> 1;
        delta[curr << 1] += delta[curr];
        delta[curr << 1 | 1] += delta[curr];
        sum[curr << 1] += delta[curr] * (mid - l + 1);
        sum[curr << 1 | 1] += delta[curr] * (r - mid);
        delta[curr] = 0;
    }
}
void add(int curr, int lb, int rb, int l, int r, int val) {
    if (l > rb || r < lb) return;
    if (l <= lb && r >= rb) {
        sum[curr] += val * (rb - lb + 1);
        delta[curr] += val;
        return;
    }
    int mid = (lb + rb) >> 1;
    pushdown(curr, lb, rb);
    add(curr << 1, lb, mid, l, r, val);
    add(curr << 1 | 1, mid + 1, rb, l, r, val);
    update(curr);
}
int query(int curr, int lb, int rb, int l, int r) {
    if (l > rb || r < lb) return 0;
    if (l <= lb && r >= rb) return sum[curr];
    pushdown(curr, lb, rb);
    int mid = (lb + rb) >> 1;
    return query(curr << 1, lb, mid, l, r) + query(curr << 1 | 1, mid + 1, rb, l, r);
}

void dfs(int x) {
    size[x] = 1; dep[x] = dep[fa[x]] + 1;
    erep(i, x) if (v[i] != fa[x]) {
        fa[v[i]] = x;
        dfs(v[i]);
        size[x] += size[v[i]];
        if (size[v[i]] > size[son[x]])
            son[x] = v[i];
    }
}
void dfs(int x, int t) {
    top[x] = t;
    dfn[x] = ++index;
    if (son[x]) dfs(son[x], t);
    erep(i, x) if (v[i] != fa[x] && v[i] != son[x])
        dfs(v[i], v[i]);
}
int query(int x, int y) {
    int ans = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
        ans += query(1, 1, n, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) std::swap(x, y);
    ans += query(1, 1, n, dfn[y], dfn[x]);
    return ans;
}
void add(int x, int y, int val) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
        add(1, 1, n, dfn[top[x]], dfn[x], val);
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) std::swap(x, y);
    add(1, 1, n, dfn[y], dfn[x], val);
}

struct Query {
    int l, r, x, a[2];
};
Query q[maxn];

struct SS {
    int x, where, which;
    SS(int xx, int we, int wi)
        : x(xx), where(we), which(wi) {}
    SS() : x(0), where(0), which(0) {}
};
std::vector<SS> b[maxn];

int main() {
    read(n, m);
    rep(i, 1, n - 1) {
        int x; read(x);
        ae(i + 1, x + 1);
    }
    dfs(1);
    dfs(1, 1);
    rep(i, 1, m) {
        read(q[i].l, q[i].r, q[i].x);
        ++q[i].l; ++q[i].r; ++q[i].x;
        b[q[i].l - 1].push_back(SS(q[i].x, i, 0));
        b[q[i].r].push_back(SS(q[i].x, i, 1));
    }
    rep(i, 1, n) {
        add(1, i, 1);
        for (unsigned j = 0; j < b[i].size(); ++j) {
            int ans = query(1, b[i][j].x);
            q[b[i][j].where].a[b[i][j].which] = ans % mod;
        }
    }
    rep(i, 1, m) printf("%d\n", ((q[i].a[1] - q[i].a[0]) % mod + mod) % mod);
    return 0;
}