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
0
0
1
1
1 4 3
1 4 2
Sample Output
8
5
5
HINT
共5组数据,n与q的规模分别为10000,20000,30000,40000,50000。
Source
数据已加强 by saffah
Solution
离线+差分询问+树链剖分
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 |
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int mo=201314,N=50010; int n,q,head[N],tot,label,Next[N],tree[N],fa[N],dep[N],son[N],size[N],top[N]; int tid[N],Tree[N*8],lazy[N*8],ans[N][2]; bool visit[N]; struct node { int u,v,w; }a[N*2]; bool cmp(node a,node b) { if (a.u<b.u) return true; return false; } void add(int x,int y) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; } void dfs1(int u,int father,int depth) { visit[u]=true;fa[u]=father;dep[u]=depth;son[u]=-1;size[u]=1; int maxsize=0; for (int i=head[u];i!=-1;i=Next[i]) if (!visit[tree[i]]) { dfs1(tree[i],u,depth+1); size[u]+=size[tree[i]]; if (size[tree[i]]>maxsize) maxsize=size[tree[i]],son[u]=tree[i]; } } void dfs2(int u,int ancestor) { visit[u]=true;top[u]=ancestor; label++;tid[u]=label; if (son[u]!=-1) dfs2(son[u],ancestor); for (int i=head[u];i!=-1;i=Next[i]) if (!visit[tree[i]]) dfs2(tree[i],tree[i]); } void down(int id,int x) { if (lazy[id]!=0) { Tree[id*2]=(Tree[id*2]+lazy[id]*(x-x/2))%mo; Tree[id*2+1]=(Tree[id*2+1]+lazy[id]*(x/2))%mo; lazy[id*2]=(lazy[id*2]+lazy[id])%mo; lazy[id*2+1]=(lazy[id*2+1]+lazy[id])%mo; lazy[id]=0; } } void up(int id) { Tree[id]=(Tree[id*2]+Tree[id*2+1])%mo; } void Change(int x,int y,int id,int l,int r,int d) { if (l>y||r<x) return; down(id,r-l+1); if (x<=l&&r<=y) { Tree[id]=(Tree[id]+(r-l+1)*d)%mo; lazy[id]=(lazy[id]+d)%mo; return; } int mid=(l+r)/2; Change(x,y,id*2,l,mid,d); Change(x,y,id*2+1,mid+1,r,d); up(id); } int Query(int x,int y,int id,int l,int r) { if (l>y||r<x) return 0; down(id,r-l+1); if (x<=l&&r<=y) return Tree[id]; int mid=(l+r)/2; return (Query(x,y,id*2,l,mid)+Query(x,y,id*2+1,mid+1,r))%mo; } void change(int u,int v) { while (top[u]!=top[v]) { Change(tid[top[u]],tid[u],1,1,n,1); u=fa[top[u]]; } Change(tid[v],tid[u],1,1,n,1); } int query(int u,int v) { int ans=0; while (top[u]!=top[v]) { ans=(ans+Query(tid[top[u]],tid[u],1,1,n))%mo; u=fa[top[u]]; } ans=(ans+Query(tid[v],tid[u],1,1,n))%mo; return ans; } int main() { scanf("%d%d",&n,&q); for (int i=0;i<=n;i++) head[i]=-1; tot=label=0; for (int i=1;i<=n-1;i++) { int x; scanf("%d",&x); add(x,i); } for (int i=0;i<n;i++) visit[i]=false; dfs1(0,0,0); for (int i=0;i<n;i++) visit[i]=false; dfs2(0,0); int num=0; for (int i=1;i<=q;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); a[++num].u=x-1;a[num].v=i;a[num].w=z; a[++num].u=y;a[num].v=i;a[num].w=z; ans[i][0]=ans[i][1]=-1; } sort(a+1,a+num+1,cmp); int j=-1; for (int i=1;i<=num;i++) { if (a[i].u==-1) { ans[a[i].v][0]=0;continue;} while (a[i].u>j) j++,change(j,0); if (ans[a[i].v][0]==-1) ans[a[i].v][0]=query(a[i].w,0); else ans[a[i].v][1]=query(a[i].w,0); } for (int i=1;i<=q;i++) printf("%d\n",(ans[i][1]-ans[i][0]+mo)%mo); return 0; } |