[LNOI2014]LCA

题目描述

给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。

设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。有q次询问，每次询问给出l r z，求$sum_{lleq i leq r}dep[lca(i,z)]$

[GXOI/GZOI2019]旧词一样。甚至这个还简单一点，就是k=1；

只是从[1,r]变成[l,r]，其实很简单，稍微差分一下机OK了，可以查询[1,r]和[1,l-1]的答案相减。

根据之前的性质可知是有可减性的。

在记录答案时，为了简单一点，同时利用r>l-1后被查询且最初数组为0的性质，直接将当前查询到的答案与之前记录的相减即可。

//差分性质，对于[l,r]的询问，可以求到[1,l-1]和[1,r]的询问，再相减 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=50005;
const int mod=201314;
int n,m;
int dep[maxn],fa[maxn],size[maxn],son[maxn];
int num,id[maxn],top[maxn];
int root,ls[maxn<<1],rs[maxn<<1],len[maxn<<1];
ll sum[maxn<<1],tag[maxn<<1];
ll get_it[maxn];
vector<int>e[maxn];
vector<pair<int,int> > q[maxn];

template<class T>void read(T &x){
    x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
}

void dfs(int u){
    size[u]=1;
    for(unsigned int i=0;i<e[u].size();i++){
        int v=e[u][i];
        dep[v]=dep[u]+1;
        dfs(v);
        size[u]+=size[v];
        if(size[son[u]]<size[v]) son[u]=v;
    }
}

void dfs(int u,int tp){
    id[u]=++num;
    top[u]=tp;
    if(!son[u]) return ;
    dfs(son[u],tp);
    for(unsigned int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==son[u]) continue;
        dfs(v,v);
    }
}

void build(int &rt,int l,int r){
    rt=++num;
    len[rt]=r-l+1;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(ls[rt],l,mid);
    build(rs[rt],mid+1,r);
}

void put_tag(int rt,int val){
    tag[rt]=(tag[rt]+val)%mod;
    sum[rt]=(sum[rt]+val*len[rt])%mod;
}

void push_down(int rt){
    put_tag(ls[rt],tag[rt]);
    put_tag(rs[rt],tag[rt]);
    tag[rt]=0;
}

void update(int rt){
    sum[rt]=(sum[ls[rt]]+sum[rs[rt]])%mod;
}

void modify(int rt,int l,int r,int a_l,int a_r){
    if(a_l<=l&&r<=a_r){
        put_tag(rt,1);
        return ;
    }
    if(tag[rt]) push_down(rt);
    int mid=(l+r)>>1;
    if(a_l<=mid) modify(ls[rt],l,mid,a_l,a_r);
    if(mid<a_r) modify(rs[rt],mid+1,r,a_l,a_r);
    update(rt);
}

void modify(int x,int y){
    while(top[x]!=top[y]){
        modify(1,1,n,id[top[y]],id[y]);
        y=fa[top[y]];
    }
    modify(1,1,n,id[x],id[y]);
}

ll query(int rt,int l,int r,int a_l,int a_r){
    if(a_l<=l&&r<=a_r) return sum[rt];
    if(tag[rt]) push_down(rt);
    int mid=(l+r)>>1;
    ll ret=0;
    if(a_l<=mid) ret+=query(ls[rt],l,mid,a_l,a_r);
    if(mid<a_r) ret+=query(rs[rt],mid+1,r,a_l,a_r);
    return ret%mod;
}

ll query(int x,int y){
    ll ret=0;
    while(top[x]!=top[y]){
        ret=(ret+query(1,1,n,id[top[y]],id[y]))%mod;
        y=fa[top[y]];
    }
    ret=(ret+query(1,1,n,id[x],id[y]))%mod;
    return ret;
}

int main(){
    read(n);read(m);
    for(int i=2;i<=n;i++){
        read(fa[i]);
        fa[i]++;
        e[fa[i]].push_back(i);
    }
    for(int i=1;i<=m;i++){
        int x,y,z;
        read(x);read(y);read(z);
        x++;y++;z++;
        q[x-1].push_back(make_pair(z,i));
        q[y].push_back(make_pair(z,i));
    }
    dfs(1);
    dfs(1,1);
    num=0;
    build(root,1,n);
    for(int i=1;i<=n;i++){
        modify(1,i);
        for(unsigned int j=0;j<q[i].size();j++){
            ll x=query(1,q[i][j].first);
            get_it[q[i][j].second]=((x-get_it[q[i][j].second])%mod+mod)%mod;
        }
    }
    for(int i=1;i<=m;i++) printf("%lld
",get_it[i]);
}

View Code

[LNOI2014]LCA

题目描述

题解