[LNOI 2014]LCA

时间：2023-03-09 00:10:16
[LNOI 2014]LCA

Description

给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。
设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。
有q次询问，每次询问给出l r z，求sigma_{l<=i<=r}dep[LCA(i,z)]。
（即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和）

Input

第一行2个整数n q。
接下来n-1行，分别表示点1到点n-1的父节点编号。
接下来q行，每行3个整数l r z。

Output

输出q行，每行表示一个询问的答案。每个答案对201314取模输出

Sample Input

5 2
0
0
1
1
1 4 3
1 4 2

Sample Output

8
5

HINT

共5组数据，n与q的规模分别为10000,20000,30000,40000,50000。

题解

[HNOI 2015]开店的简化版。

 //It is made by Awson on 2018.1.8

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define RE register

 #define lowbit(x) ((x)&(-(x)))

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

 using namespace std;

 const int N = ;

 const int MOD = ;

 const int INF = ~0u>>;

 int n, q, f, u, v, c, fa[N+], dep[N+], top[N+], cnt, size[N+], son[N+], pos[N+];

 struct tt {

     int to, next;

 }edge[N+];

 int path[N+], tot;

 void add(int u, int v) {

     edge[++tot].to = v;

     edge[tot].next = path[u];

     path[u] = tot;

 }

 struct Segment_tree {

     int root[N+], sum[N*+], lazy[N*+], ch[N*][], pos;

     int newnode(int r) {

     int o = ++pos; sum[o] = sum[r], lazy[o] = lazy[r], ch[o][] = ch[r][], ch[o][] = ch[r][];

     return o;

     }

     void update(int &o, int l, int r, int a, int b, int last) {

        if (o <= last) o = newnode(o);

     if (a <= l && r <= b) {

         sum[o] += r-l+, sum[o] %= MOD, lazy[o]++; return;

     }

     int mid = (l+r)>>;

     if (mid >= a) update(ch[o][], l, mid, a, b, last);

     if (mid < b) update(ch[o][], mid+, r, a, b, last);

     sum[o] = (sum[ch[o][]]+sum[ch[o][]]+(LL)lazy[o]*(r-l+)%MOD)%MOD;

     }

     int query(int o, int l, int r, int a, int b) {

     if (!o) return ;

     if (a <= l && r <= b) return sum[o];

     int mid = (l+r)>>, c1 = , c2 = ;

     if (mid >= a) c1 = query(ch[o][], l, mid, a, b);

     if (mid < b) c2 = query(ch[o][], mid+, r, a, b);

     return (c1+c2+(LL)lazy[o]*(Min(r, b)-Max(l, a)+)%MOD)%MOD;

     }

 }T;

 void dfs1(int o, int father, int depth) {

     fa[o] = father, dep[o] = depth+, size[o] = ;

     for (int i = path[o]; i; i = edge[i].next) {

     dfs1(edge[i].to, o, depth+);

     size[o] += size[edge[i].to];

     if (size[edge[i].to] > size[son[o]]) son[o] = edge[i].to;

     }

 }

 void dfs2(int o, int tp) {

     top[o] = tp, pos[o] = ++cnt;

     if (son[o]) dfs2(son[o], tp);

     for (int i = path[o]; i; i = edge[i].next)

     if (edge[i].to != son[o]) dfs2(edge[i].to, edge[i].to);

 }

 void lca_update(int id, int o, int last) {while (top[o]) T.update(T.root[id], , n, pos[top[o]], pos[o], last), o = fa[top[o]]; }

 int lca_query(int id, int o) {

     int ans = ;

     while (top[o]) ans += T.query(T.root[id], , n, pos[top[o]], pos[o]), ans %= MOD, o = fa[top[o]];

     return ans;

 }

 void work() {

     scanf("%d%d", &n, &q);

     for (int i = ; i <= n; i++) scanf("%d", &f), add(f+, i);

     dfs1(, , ), dfs2(, );

     for (int i = ; i <= n; i++) {

     T.root[i] = T.root[i-]; lca_update(i, i, T.pos);

     }

     while (q--) {

     scanf("%d%d%d", &u, &v, &c);

     printf("%d\n", (lca_query(v+, c+)-lca_query(u, c+)+MOD)%MOD);

     }

 }

 int main() {

     work();

     return ;

 }

相关文章