看题目是个板子题诶~做这个题还得被机友嘲讽只会切板子题......
好那先看板子题的题目吧~
题目描述
给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。 设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。 有q次询问，每次询问给出l r z，求∑(l,r)dep[LCA(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。
考虑暴力做。如果我们把所有的LCA求出来，那么就可能要求50000x50000次。树上倍增求LCA肯定会爆对吧......然后我们考虑Tarjan——虽然是线性但是也不是用来跑这种数据的吧!!!估计暴力的话一组也过不了。试试优化？反正我是没想到优化
学了这么久OI，你想想，什么东西是最好优化的？暴力！那刚才的东西为什么优化不出来？因为还不够暴力(啪!)。假如你既不会树上倍增又不会Tarjan，让你求LCA你会怎么求？很明显，我们只需要从一对询问中的一个点出发往根走，走过的点都标记起来；然后从另一个点向根走，走到的第一个被标记过的点就是LCA。显然我们这题也可以这样做。首先l~r和z的所有LCA肯定在z的上方，这些LCA都对答案有所贡献。再看，什么是深度呢？虽然题目里面定义得十分简单明了，但我们可以把它看成：这个点到根节点一共有多少点。那我们暴力从l~r的所有点开始都往根节点走，把走过的每一个点的权值都加1。最后再从z往根节点走，把所有走过的点的权值都加起来就是答案了。然而还是可怜的O(qn2)......有了这么暴力的一个玩意儿，现在就可以开始优化了！首先，往根节点走，把路径上每个点的权值都加1，最后还要求出权值和......这不是树剖应该做的东西吗？于是，对于每次操作，我们就可以把O(n)的复杂度降成O(lognlogn)。然而复杂度还是很高O(qnlog2n)。这是在线算法的复杂度，不如想想离线？如果我有一种方法把所有询问一起处理，就可以优化掉这个q，再看看数据范围，应该O(nlog2n)就可以过了。怎么优化？
对于每个询问l,r,z，它要求的是∑(l,r)dep[LCA(i,z)]，运用前缀和的思想，我们把这个式子看成：∑(1,r)dep[LCA(i,z)]-∑(1,l-1)dep[LCA(i,z)]。所以我们可以先求出所有的dep[LCA(i,z)](1<=i<=max{r})，也就是枚举每个i，然后用树链剖分的线段树部分去修改i~根节点的路径上每个点的权值。当枚举到一个i是某个询问里的z时，就查询一下i~根节点的路径上的权值和。这样一来，复杂度就降成了O(nlog2n)。
代码部分：
#include<algorithm> #include<cstring> #include<cstdio> #define maxn 500001 #define maxm 500001 #define p 201314 using namespace std; struct edge{ int to,next; edge(){} edge(const int &_to,const int &_next){ to=_to,next=_next; } }e[maxn<<1]; int head[maxn],k; struct question{ int id,to,lca;//分别表示：询问的编号(因为要按顺序输出)、要求的是∑(1,to)dep[LCA(i,z)]，和询问中的z bool flag;//true表示to为询问中的l，false表示to是询问中的r question(){} question(const int &_id,const int &_to,const int &_lca,const bool &_flag){ id=_id,to=_to,lca=_lca,flag=_flag; } bool operator<(const question &q) const{ return to<q.to; }//从小到大排序，顺序枚举 }q[maxm<<1]; struct node{ int l,r,c,f; }t[maxn<<2];//线段树 int size[maxn],dep[maxn],fa[maxn],son[maxn]; int top[maxn],dfn[maxn],id[maxn],tot; int n,m,d,ans[2][maxm];//ans[1][j]表示第j个询问中的∑(1,l-1)dep[LCA(i,z)],ans[0][j]表示第j个询问中的∑(1,r)dep[LCA(i,z)]，最后的答案就是ans[0][j]-ans[1][j] inline int read(){ register int x(0); register char c(getchar()); while(c<'0'||'9'<c) c=getchar(); while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x; }//快读 inline int add(const int &u,const int &v){ e[k]=edge(v,head[u]); head[u]=k++; }//存边 void dfs_getson(int u){ size[u]=1; int v; for(register int i=head[u];~i;i=e[i].next){ v=e[i].to; if(v==fa[u]) continue; fa[v]=u,dep[v]=dep[u]+1; dfs_getson(v); size[u]+=size[v]; if(size[v]>size[son[u]]) son[u]=v; } } void dfs_rewrite(int u,int tp){ top[u]=tp,dfn[u]=++tot,id[tot]=u; if(son[u]) dfs_rewrite(son[u],tp); int v; for(register int i=head[u];~i;i=e[i].next){ v=e[i].to; if(v!=fa[u]&&v!=son[u]) dfs_rewrite(v,v); } } void build(int d,int l,int r){ t[d].l=l,t[d].r=r; if(l==r) return; int mid=l+r>>1; build(d<<1,l,mid),build(d<<1|1,mid+1,r); } inline void down(const int &d){ t[d<<1].c=(t[d<<1].c+t[d].f*(t[d<<1].r-t[d<<1].l+1)%p)%p; t[d<<1|1].c=(t[d<<1|1].c+t[d].f*(t[d<<1|1].r-t[d<<1|1].l+1)%p)%p; t[d<<1].f=(t[d<<1].f+t[d].f)%p,t[d<<1|1].f=(t[d<<1|1].f+t[d].f)%p; t[d].f=0; }//下传延迟标记 void change(int d,const int &l,const int &r){ if(l<=t[d].l&&t[d].r<=r){ t[d].c=(t[d].c+t[d].r-t[d].l+1)%p,t[d].f=(t[d].f+1)%p; return; } if(t[d].f) down(d); int mid=t[d].l+t[d].r>>1; if(l<=mid) change(d<<1,l,r); if(r>mid) change(d<<1|1,l,r); t[d].c=(t[d<<1].c+t[d<<1|1].c)%p; }//区间修改 int getsum(int d,const int &l,const int &r){ if(l<=t[d].l&&t[d].r<=r) return t[d].c; if(t[d].f) down(d); int mid=t[d].l+t[d].r>>1,ans=0; if(l<=mid) ans=(ans+getsum(d<<1,l,r))%p; if(r>mid) ans=(ans+getsum(d<<1|1,l,r))%p; return ans; }//区间查询 inline void change_path(int v){ while(top[v]!=1){ change(1,dfn[top[v]],dfn[v]); v=fa[top[v]]; } change(1,1,dfn[v]); } inline int getsum_path(int v){ int ans=0; while(top[v]!=1){ ans=(ans+getsum(1,dfn[top[v]],dfn[v])); v=fa[top[v]]; } ans=(ans+getsum(1,1,dfn[v]))%p; return ans; } int main(){ memset(head,-1,sizeof head); n=read(),m=read(); int u; for(register int i=2;i<=n;i++){ u=read()+1; add(u,i),add(i,u); }//存树 dfs_getson(1); dfs_rewrite(1,1);//树链剖分 build(1,1,tot);//构造线段树 int l,r,z; for(register int i=1;i<=m;i++){ l=read(),r=read()+1,z=read()+1; q[++d]=question(i,l,z,true); q[++d]=question(i,r,z,false);//把询问存起来——true表示的是l的询问，false是r的询问 } sort(q+1,q+1+d); int now=0; register int tmp; for(register int i=1;i<=d;i++){ while(now<q[i].to) change_path(++now);//枚举并修改路径上的权值 ans[q[i].flag][q[i].id]=getsum_path(q[i].lca);//查询路径上的权值 } for(register int i=1;i<=m;i++){ printf("%d ",(ans[0][i]-ans[1][i]+p)%p); }//输出 return 0; }
要注意的点：
1.把题中输入的点编号全部加1，询问也要加
2.最后的ans相减之后判负数
其实蒟蒻因为敲错了快读卡了半天