题目链接：https://www.luogu.com.cn/problem/P4211
题目大意：给定一棵有根树，对于 (q) 个询问 (l, r, z), 求 (sumlimits_{l leq i leq r} {depth(Lca(i, z))})
solution
考虑另一个问题：求出(sumlimits_{i leq n} {depth(Lca(i, z))}) , 此问题可以转化为 (i) 从 1 到 (n), 分别把 1 到 (i) 路径上的所有点权值加 1, 再求 从根 到 (z) 路径上的权值之和
不难发现 , 原问题可以转化为(sumlimits_{i leq r} {depth(Lca(i, z))} - sumlimits_{i leq l - 1} {depth(Lca(i, z))}) , 可以把原问题分解成两个子问题并离线 , 从 1 到 (n) 分别用树剖修改 , 在此过程中同时算出子问题的答案 , 最后统计即可
时间复杂度: (O(nlog^2n))
code
#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &FF) {
int RR = 1; FF = 0; char CH = getchar();
for(; !isdigit(CH); CH = getchar()) if(CH == '-') RR = -RR;
for(; isdigit(CH); CH = getchar()) FF = FF * 10 + CH - 48;
FF *= RR;
}
inline void file(string str) {
freopen((str + ".in").c_str(), "r", stdin);
freopen((str + ".out").c_str(), "w", stdout);
}
#define mod 201314
const int N = 1e5 + 10;
int now, fst[N], nxt[N], num[N], l[N], r[N], z[N], rs[N], dep[N];
int n, q, si, ni, pi = 1, size[N], son[N], fa[N], tp[N], rev[N], sg[N];
void add(int u, int v) {
nxt[++now] = fst[u], fst[u] = now, num[now] = v;
nxt[++now] = fst[v], fst[v] = now, num[now] = u;
}
struct Segment_tree{
int val, tag;
}xds[N << 2];
struct Que{
int qi, fi, id, fl;
friend bool operator < (Que ai, Que bi) {
return ai.qi < bi.qi;
}
}qy[N];
void push_up(int pos) {
xds[pos].val = (xds[pos << 1].val + xds[pos << 1 | 1].val) % mod;
}
void Add(int pos, int l, int r, int ki) {
xds[pos].val = (xds[pos].val + (r - l + 1) * ki % mod) % mod;
xds[pos].tag = (xds[pos].tag + ki) % mod;
}
void push_down(int pos, int l, int r) {
if(xds[pos].tag == 0) return;
int mid = (l + r) >> 1;
Add(pos << 1, l, mid, xds[pos].tag);
Add(pos << 1 | 1, mid + 1, r, xds[pos].tag);
xds[pos].tag = 0;
}
void modify(int pos, int l, int r, int ll, int rr) {
if(l >= ll && r <= rr) {
Add(pos, l, r, 1);
return;
}
push_down(pos, l, r); int mid = (l + r) >> 1;
if(mid >= ll) modify(pos << 1, l, mid, ll, rr);
if(mid < rr) modify(pos << 1 | 1, mid + 1, r, ll, rr);
push_up(pos);
}
int query(int pos, int l, int r, int ll, int rr) {
if(l >= ll && r <= rr) return xds[pos].val;
push_down(pos, l, r); int mid = (l + r) >> 1, res = 0;
if(mid >= ll) res = (res + query(pos << 1, l, mid, ll, rr)) % mod;
if(mid < rr) res = (res + query(pos << 1 | 1, mid + 1, r, ll, rr)) % mod;
// push_up(pos);
return res;
}
void tree_dsu(int xi) {
size[xi] = 1; dep[xi] = dep[fa[xi]] + 1;
for(int i = fst[xi]; i; i = nxt[i])
if(num[i] != fa[xi]) {
tree_dsu(num[i]);
size[xi] += size[num[i]];
if(size[num[i]] > size[son[xi]])
son[xi] = num[i];
}
}
void tree_pre(int xi) {
if(son[xi]) {
tp[son[xi]] = tp[xi], sg[++si] = son[xi];
rev[son[xi]] = si, tree_pre(son[xi]);
}
for(int i = fst[xi]; i; i = nxt[i])
if(num[i] != son[xi] && num[i] != fa[xi]) {
tp[num[i]] = num[i], sg[++si] = num[i];
rev[num[i]] = si, tree_pre(num[i]);
}
}
void modify_list(int xi) {
int yi = 1;
while(tp[xi] != tp[yi]) {
if(dep[tp[xi]] < dep[tp[yi]]) swap(xi, yi);
modify(1, 1, n, rev[tp[xi]], rev[xi]);
xi = fa[tp[xi]];
}
if(dep[xi] > dep[yi]) swap(xi, yi);
modify(1, 1, n, rev[xi], rev[yi]);
}
int query_list(int xi) {
int yi = 1, res = 0;
while(tp[xi] != tp[yi]) {
if(dep[tp[xi]] < dep[tp[yi]]) swap(xi, yi);
res = (res + query(1, 1, n, rev[tp[xi]], rev[xi])) % mod;
xi = fa[tp[xi]];
}
if(dep[xi] > dep[yi]) swap(xi, yi);
res = (res + query(1, 1, n, rev[xi], rev[yi])) % mod;
return res;
}
int main() {
//file("");
read(n), read(q);
for(int i = 2; i <= n; i++) {
read(fa[i]); fa[i]++;
add(fa[i], i);
}
tp[1] = rev[1] = sg[1] = si = 1;
tree_dsu(1), tree_pre(1);
for(int i = 1; i <= q; i++) {
read(l[i]), read(r[i]), read(z[i]); l[i]++, r[i]++, z[i]++;
if(l[i] != 1) qy[++ni].qi = l[i] - 1, qy[ni].id = i, qy[ni].fi = z[i], qy[ni].fl = -1;
qy[++ni].qi = r[i], qy[ni].id = i, qy[ni].fi = z[i], qy[ni].fl = 1;
}
sort(qy + 1, qy + ni + 1);
for(int i = 1; i <= n; i++) {
modify_list(i);
// cout << query(1, 1, n, sg[2], sg[2]) << endl;
while(pi <= ni && qy[pi].qi == i)
rs[qy[pi].id] += qy[pi].fl * query_list(qy[pi].fi), pi++;
}
for(int i = 1; i <= q; i++)
cout << (rs[i] + mod) % mod << endl;
return 0;
}