Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 4707 Solved: 2001
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。
/**************************************************************
Problem: 3626
User: ictsing
Language: C++
Result: Accepted
Time:1700 ms
Memory:12712 kb
****************************************************************/
//BZOJ3626 [LNOI2014]LCA
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int mt = 100000+5;
int to[mt<<1],nxt[mt<<1],adj[mt];
int sum[mt<<2],tag[mt<<2];
int ecnt=0;
typedef long long ll;
int n;
const int mod = 201314;
inline int read()
{
int num=0,flag=1;
char ch;
do{
ch=getchar();
if(ch=='-') flag=-1;
}while(ch<'0'||ch>'9');
do{
num=num*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return num*flag;
}
void adde(int u,int v)
{
ecnt++,to[ecnt]=v,nxt[ecnt]=adj[u],adj[u]=ecnt;
}
int sz[mt],opt[mt];
int top[mt],place[mt];
int fa[mt],dep[mt];
int tot=0;
void dfs1(int u)
{
dep[u]=dep[fa[u]]+1,sz[u]=1;
for(int i=adj[u];i;i=nxt[i])
{
int v=to[i];
if(v^fa[u])
{
fa[v]=u;
dfs1(v);
sz[u]+=sz[v];
if(sz[v]>sz[opt[u]])
opt[u]=v;
}
}
}
void dfs2(int u,int chain)
{
top[u]=chain;
place[u]=++tot;
if(opt[u]) dfs2(opt[u],chain);
else return ;
for(int i=adj[u];i;i=nxt[i])
{
int v=to[i];
if(fa[u]^v&&opt[u]^v)
dfs2(v,v);
}
}
struct ques{
int x,y,z,id;
}q[mt<<1];
bool cmp(ques a,ques b)
{
return a.x<b.x;
}
ll ans[mt];
void pushdown(int rt,int l,int r)
{
if(tag[rt])
{
int mid=(l+r)>>1;
sum[rt<<1]+=(mid-l+1)*tag[rt];
sum[rt<<1|1]+=(r-mid)*tag[rt];
tag[rt<<1]+=tag[rt];
tag[rt<<1|1]+=tag[rt];
tag[rt]=0;
}
}
void pushup(int rt)
{
if(rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
}
void add(int rt,int l,int r,int lft,int rgt,int x)
{
if(lft<=l&&r<=rgt)
{
sum[rt]+=(r-l+1)*x;
tag[rt]+=x;
return ;
}
pushdown(rt,l,r);
int mid=(l+r)>>1;
if(lft<=mid) add(rt<<1,l,mid,lft,rgt,x);
if(rgt>mid) add(rt<<1|1,mid+1,r,lft,rgt,x);
pushup(rt);
}
ll query(int rt,int l,int r,int lft,int rgt)
{
if(lft<=l&&r<=rgt)
{
return sum[rt];
}
pushdown(rt,l,r);
int mid=(l+r)>>1;
ll ans=0;
if(lft<=mid) ans+=query(rt<<1,l,mid,lft,rgt);
if(rgt>mid) ans+=query(rt<<1|1,mid+1,r,lft,rgt);
return ans;
}
void lca_insrt(int u)
{
while(u)
{
int v=top[u];
add(1,1,n,place[v],place[u],1);
u=fa[v];
}
}
ll lca_query(int u)
{
ll res=0;
while(u)
{
int v=top[u];
res+=query(1,1,n,place[v],place[u]);
u=fa[v];
}
return res;
}
int main()
{
n=read();
int m=read();
for(int i=2;i<=n;i++)
{
fa[i]=read();fa[i]++;
adde(i,fa[i]),adde(fa[i],i);
}
dfs1(1);
dfs2(1,1);
memset(sum,0,sizeof(sum));
memset(tag,0,sizeof(tag));
for(int i=1;i<=m;i++)
{
int a=read(),b=read(),c=read();
a++,b++,c++;
q[i*2-1].x=a-1,q[i*2-1].y=c,q[i*2-1].z=-1,q[i*2-1].id=i;
q[i*2].x=b,q[i*2].y=c,q[i*2].z=1,q[i*2].id=i;
}
sort(q+1,q+2*m+1,cmp);
//for(int i=1;i<=n;i++)
//cout<<place[i]<<" ovo "<<endl;
for(int i=0,j=1;i<=n;i++)
{
lca_insrt(i);
for(;q[j].x==i;j++)
{
ans[q[j].id]+=q[j].z*lca_query(q[j].y);
//cout<<q[j].id<<" qwq "<<ans[q[j].id]<<endl;
}
}
for(int i=1;i<=m;i++)
printf("%lld\n",ans[i]%mod);
return 0;
}
评论