Description

A rooted tree with n nodes (numbered 0 to n-1 and root node 0) is given. The depth of a point is defined as the distance from the node to the root + 1.
Let dep[i] denote the depth of point I and LCA(i,j) denote the recent common ancestors of point I and J.
There are q inquiries, each inquiry gives l r z, sigma_{l<=i<=r} dep [LCA(i, z)].
(i.e., the sum of the depths of the nearest common ancestors of each node i and z in the [l,r] interval)

Input

The first row has two integers n q.
Next, line n-1 denotes the parent node numbers from point 1 to point n-1, respectively.
Next, line q, with three integers l r z per line.

Output

Output q lines, each representing an answer to a query. Modular output for 201314 for each answer

Title Solution

This topic strength tree chain division ah.
First of all, there are no people who can do it online, but it's hard to think offline.
Then, let's simplify it and deal with a group of questions.
The idea of violence is that we mark every point we want to ask and then look up z. The first marked point we encounter is their LCA.
Then we can see that the depth of each tag is equal to how many tags it has on it. So we can add + 1 to the path from each point to the root, and then ask z to the sum of the roots, and that's the answer.
It's obvious that tree chains can be used.
So many groups of inquiries:
The answer of interval [l,r] is the answer of interval [1,r] - the answer of interval [1,l-1].
So let's break each query into two, one plus and one minus. Then sort and update from 1 to N in order.

Code

#include<cstdio>
#include<cstring>
#include<algorithm>

#define N 50010
#define mod 201314
using namespace std;

struct node{int to,next;}e[N*2];
int head[N],m,tim,n;
int dep[N],size[N],top[N],fa[N],son[N],tid[N];
int ans[N];
struct data{int p,num,w,f;}a[N*2];
inline bool operator < (data a,data b) { return a.p < b.p; }

void init() {
    tim = m = 0;
    memset(head,0,sizeof(head));
    memset(son,-1,sizeof(son));
}

void add_edge(int from,int to) {
    e[++m].next = head[from];
    head[from] = m;
    e[m].to = to;
}

void dfs1(int v,int d) {
    dep[v] = d; size[v] = 1;
    for(int i = head[v];i;i=e[i].next) {
        dfs1(e[i].to,d+1);
        size[v] += size[e[i].to];
        if(son[v] == -1 || size[e[i].to] > size[son[v]])
            son[v] = e[i].to;
    }
}

void dfs2(int v,int tp) {
    tid[v] = ++tim; top[v] = tp;
    if(son[v] == -1) return;
    dfs2(son[v],tp);
    for(int i = head[v];i;i=e[i].next)
        if(e[i].to != son[v])
            dfs2(e[i].to,e[i].to);
}

#define lson o << 1
#define rson o << 1 | 1
int sum[N << 2],add[N << 2];

void build(int o,int l,int r)
{
    sum[o] = 0;
    if(l == r) return;
    int mid = (l+r)>>1;
    build(lson,l,mid); build(rson,mid+1,r);
}

void pushdown(int o,int l,int r)
{
    if(add[o] != 0) {
        int mid = (l+r)>>1;
        add[lson] += add[o]; sum[lson] += (mid-l+1)*add[o];
        add[rson] += add[o]; sum[rson] += (r-mid)*add[o];
        add[o] = 0;
    }
}

void update(int o,int l,int r,int ll,int rr)
{
    if(ll <= l && rr >= r) {add[o]++;sum[o]+=(r-l+1);return;}
    int mid = (l+r)>>1;
    pushdown(o,l,r);
    if(ll <= mid) update(lson,l,mid,ll,rr);
    if(rr > mid) update(rson,mid+1,r,ll,rr);
    sum[o] = sum[lson] + sum[rson];
}

void change(int x,int y)
{
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        update(1,1,n,tid[top[x]],tid[x]);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x,y);
    update(1,1,n,tid[x],tid[y]);
}

int query(int o,int l,int r,int ll,int rr)
{
    if(ll <= l && rr >= r)return sum[o];
    int mid = (l+r)>>1,ans = 0;
    pushdown(o,l,r);
    if(ll <= mid) ans += query(lson,l,mid,ll,rr);
    if(rr > mid) ans += query(rson,mid+1,r,ll,rr);
    return ans;
}

int ask(int x,int y)
{
    int ans = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        ans += query(1,1,n,tid[top[x]],tid[x]);
        x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x,y);
    ans += query(1,1,n,tid[x],tid[y]);
    return ans;
}

int main()
{
    int q,u,v,z,tot = 0,now = 0;
    scanf("%d%d",&n,&q);
    init();
    for(int i = 2;i <= n;i++) {
        scanf("%d",&fa[i]); fa[i]++;
        add_edge(fa[i],i);
    }
    dfs1(1,0); dfs2(1,1);
    build(1,1,n);
    for(int i = 1;i <= q;i++) {
        scanf("%d%d%d",&u,&v,&z);
        u++;v++;z++;
        a[++tot].p = u-1,a[tot].num = i,a[tot].w = z,a[tot].f = -1;
        a[++tot].p = v,a[tot].num = i,a[tot].w = z,a[tot].f = 1;
    }
    sort(a+1,a+tot+1);
    for(int i = 1;i <= tot;i++) {
        while(now < a[i].p) {
            now++;
            change(1,now);
        }
        ans[a[i].num] += a[i].f * ask(1,a[i].w);
    }
    for(int i = 1;i <= q;i++) printf("%d\n",(ans[i]+mod) % mod);
    return 0;
}