BZOJ 3626 [LNOI2014]LCA

给出一个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的最近公共祖先的深度之和）

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

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

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

一道树剖好题，转一篇题解。

直接复制gconeice的题解吧 

显然，暴力求解的复杂度是无法承受的。
考虑这样的一种暴力，我们把 z 到根上的点全部打标记，对于 l 到 r 之间的点，向上搜索到第一个有标记的点求出它的深度统计答案。观察到，深度其实就是上面有几个已标记了的点（包括自身）。所以，我们不妨把 z 到根的路径上的点全部 +1，对于 l 到 r 之间的点询问他们到根路径上的点权和。仔细观察上面的暴力不难发现，实际上这个操作具有叠加性，且可逆。也就是说我们可以对于 l 到 r 之间的点 i，将 i 到根的路径上的点全部 +1, 转而询问 z 到根的路径上的点（包括自身）的权值和就是这个询问的答案。把询问差分下，也就是用 [1, r] ? [1, l ? 1] 来计算答案，那么现在我们就有一个明显的解法。从 0 到 n ? 1 依次插入点 i，即将 i 到根的路径上的点全部+1。离线询问答案即可。我们现在需要一个数据结构来维护路径加和路径求和，显然树链剖分或LCT 均可以完成这个任务。树链剖分的复杂度为 O((n + q)· log n · log n)，LCT的复杂度为 O((n + q)· log n)，均可以完成任务。至此，题目已经被我们完美解决。

写得非常清晰明了，然而智障的窝在插入点时从1开始，而不是从0开始，调试了一晚上。

事实证明，对拍查错只用了20分钟，静态查错不靠谱啊。

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int N=50005;
const int p=201314;
int n,m,mct,dcnt,hd[N];
struct edge
{int to,nxt;
}v[N];
struct node
{int son,sz,dep,tp,w,fa;
}tr[N];
struct segtree
{int l,r,tag,sum;
}st[4*N];
struct que
{int pos,id,ans,ori;
}q[2*N];
void addedge(int x,int y)
{v[++mct].to=y;v[mct].nxt=hd[x];hd[x]=mct;
}
bool cmp1(que c,que d)
{return c.pos<d.pos;
}
bool cmp2(que c,que d)
{return c.id<d.id;
}
void dfs1(int u)
{tr[u].sz=1;for(int i=hd[u];i;i=v[i].nxt){tr[v[i].to].fa=u;tr[v[i].to].dep=tr[u].dep+1;dfs1(v[i].to);tr[u].sz+=tr[v[i].to].sz;if(tr[v[i].to].sz>tr[tr[u].son].sz)tr[u].son=v[i].to;}
}
void dfs2(int u,int top)
{tr[u].tp=top;tr[u].w=++dcnt;if(tr[u].son){dfs2(tr[u].son,top);for(int i=hd[u];i;i=v[i].nxt)if(v[i].to!=tr[u].son)dfs2(v[i].to,v[i].to);}
}
void pushup(int num)
{st[num].sum=(st[2*num].sum+st[2*num+1].sum)%p;
}
void pushdown(int num)
{if(st[num].tag){if(st[num].l!=st[num].r){st[2*num].sum=(st[2*num].sum+st[num].tag*(st[2*num].r-st[2*num].l+1))%p;st[2*num+1].sum=(st[2*num+1].sum+st[num].tag*(st[2*num+1].r-st[2*num+1].l+1))%p;st[2*num].tag+=st[num].tag;st[2*num+1].tag+=st[num].tag;}st[num].tag=0;}
}
void build(int num,int l,int r)
{st[num].l=l,st[num].r=r;if(l==r)return ;int mid=(l+r)/2;build(2*num,l,mid),build(2*num+1,mid+1,r);
}
void change(int num,int x,int y)//区间+1 
{if(st[num].l>y||st[num].r<x)return ;if(st[num].l>=x&&st[num].r<=y){st[num].sum=(st[num].sum+st[num].r-st[num].l+1)%p;st[num].tag++;return ;}pushdown(num);change(2*num,x,y),change(2*num+1,x,y);pushup(num);
}
int query(int num,int x,int y)
{if(st[num].l>y||st[num].r<x)return 0;if(st[num].l>=x&&st[num].r<=y)return st[num].sum;pushdown(num);return (query(2*num,x,y)+query(2*num+1,x,y))%p;
}
void add(int x)
{while(x){change(1,tr[tr[x].tp].w,tr[x].w);x=tr[tr[x].tp].fa;}
}
int ask(int x)
{int res=0;while(x){res+=query(1,tr[tr[x].tp].w,tr[x].w),res%=p;x=tr[tr[x].tp].fa;}return res;
}
int main()
{scanf("%d%d",&n,&m);for(int i=2;i<=n;i++){int x;scanf("%d",&x);addedge(x+1,i);}dfs1(1);dfs2(1,1);build(1,1,n);for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);++y,++z;q[2*i-1].id=2*i-1,q[2*i-1].ori=z,q[2*i-1].pos=x;q[2*i].id=2*i,q[2*i].ori=z,q[2*i].pos=y;}sort(q+1,q+2*m+1,cmp1);for(int j=1,i=0;i<=n;i++){add(i);for(;q[j].pos==i;j++)q[j].ans=ask(q[j].ori);}sort(q+1,q+2*m+1,cmp2);for(int i=1;i<=m;i++)printf("%d\n",((q[2*i].ans-q[2*i-1].ans)%p+p)%p);return 0;
}