Chrysanthemum's Blog

Description

Input

Output

Sample Input

Sample Output

HINT

题解：我们可以先将问题转化一下，求lca的深度之和就是lca及其上面的点数之和，因此暴力可以这样打，把l~r所有点到根节点的路径上每个点的权值加1，答案就是z到根节点的路径上所有点的权值之和。然而，这时间复杂度是n³的。但这优化非常容易，我们只要把询问离线处理，l~r的答案就是（0~r）-（0~l-1），所以我们只要每次0~n-1中加n这个点，将n到根节点所有点权值加1，然后处理答案。这个用树剖轻松解决。总时间复杂度O（n*logn*logn),完美解决此题。

代码：

/**************************************************************
    Problem: 3626
    User: yeweining
    Language: C++
    Result: Accepted
    Time:2876 ms
    Memory:9816 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
#include<iostream>
#define mod 201314
#define N 50010
using namespace std;
int n,q,v,edgenum,Edgenum,tot;
int vet[2*N],next[2*N],head[2*N],Vet[2*N],Next[2*N],Head[2*N],Id[2*N],Calc[2*N],x[N],y[N],z[N],ans[N];
int f[N],d[N],num[N],son[N],top[N],tid[N],pre[N];
struct node{int l,r,sum,tag;}tr[4*N];
void add(int u,int v)
{
    edgenum++;
    vet[edgenum]=v;
    next[edgenum]=head[u];
    head[u]=edgenum;
}
void Add(int u,int v,int w,int opt)
{
    Edgenum++;
    Vet[Edgenum]=v;
    Next[Edgenum]=Head[u];
    Head[u]=Edgenum;
    Id[Edgenum]=w;
    Calc[Edgenum]=opt;
}
void dfs(int u,int fa,int dep)
{
    f[u]=fa;
    d[u]=dep;
    num[u]=1;
    int maxnum=0;
    for (int e=head[u];e;e=next[e])
    {
        int v=vet[e];
        if (v!=fa)
        {
            dfs(v,u,dep+1);
            num[u]+=num[v];
            if (num[v]>maxnum){maxnum=num[v];son[u]=v;}
        }
    }
}
void dfs(int u,int number)
{
    top[u]=number;
    tid[u]=++tot;
    pre[tot]=u;
    if (!son[u]) return;
    dfs(son[u],number);
    for (int e=head[u];e;e=next[e])
    {
        int v=vet[e];
        if (v!=f[u]&&v!=son[u]) dfs(v,v);
    }
}
void build(int l,int r,int p)
{
    tr[p].l=l;tr[p].r=r;tr[p].sum=tr[p].tag=0;
    if (l==r) return;
    int mid=(l+r)>>1;
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
}
void pushdown(int p)
{
    int l=tr[p].l,r=tr[p].r;
    int mid=(l+r)>>1;
    if (l!=r)
    {
        tr[p*2].tag+=tr[p].tag;
        tr[p*2+1].tag+=tr[p].tag;
    }
    tr[p].sum+=tr[p].tag*(r-l+1);
    tr[p].sum%=mod;
    tr[p].tag=0;
}
void update(int p)
{
    pushdown(p*2);
    pushdown(p*2+1);
    tr[p].sum=tr[p*2].sum+tr[p*2+1].sum;
    tr[p].sum%=mod;
}
void change(int p,int x,int y)
{
    int l=tr[p].l,r=tr[p].r;
    pushdown(p);
    if (l==x&&y==r){tr[p].tag+=1;return;}
    int mid=(l+r)>>1;
    if (y<=mid) change(p*2,x,y);else
    if (x>mid) change(p*2+1,x,y);else
    {change(p*2,x,mid);change(p*2+1,mid+1,y);}
    update(p);
}
void update(int u,int v)
{
    while (top[u]!=top[v]) {change(1,tid[top[u]],tid[u]);u=f[top[u]];}
    change(1,tid[v],tid[u]);
}
int ask(int p,int x,int y)
{
    int l=tr[p].l,r=tr[p].r;
    pushdown(p);
    if (l==x&&y==r) return tr[p].sum;
    int mid=(l+r)>>1;
    if (y<=mid) return ask(p*2,x,y);else
    if (x>mid) return ask(p*2+1,x,y);else
    return (ask(p*2,x,mid)+ask(p*2+1,mid+1,y))%mod;
}
int get(int u,int v)
{
    int ans=0;
    while (top[u]!=top[v]) {ans+=ask(1,tid[top[u]],tid[u]);ans%=mod;u=f[top[u]];}
    ans+=ask(1,tid[v],tid[u]);
    ans%=mod;
    return ans;
}
int main()
{
    scanf("%d%d",&n,&q);
    for (int i=2;i<=n;i++)
    {
        scanf("%d",&v);
        v++;
        add(v,i);
    }
    for (int i=1;i<=q;i++)
    {
        scanf("%d%d%d",&x[i],&y[i],&z[i]);
        x[i]++;y[i]++;z[i]++;
        if (x[i]>y[i]) swap(x[i],y[i]);
        Add(x[i]-1,z[i],i,-1);Add(y[i],z[i],i,1);
    }
    dfs(1,0,1);
    dfs(1,1);
    build(1,n,1);
    for (int i=1;i<=n;i++)
    {
        update(i,1);
        for (int e=Head[i];e;e=Next[e])
        {
            int v=Vet[e];
            ans[Id[e]]+=(mod+Calc[e]*get(v,1))%mod;
            ans[Id[e]]%=mod;
        }
    }
    for (int i=1;i<=q;i++) printf("%d\n",ans[i]%mod);
}