给出一个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的最近公共祖先的深度之和)
给出一个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。
未解决
bzoj上WA了,和qt666拍了极限数据没WA,我还能干什么
1 #include <iostream> 2 #include <iomanip> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <cmath> 6 #include <cstring> 7 #include <string> 8 #include <algorithm> 9 #define int long long 10 #define RG register 11 const int N = 500000; 12 const int mod=201314; 13 14 using namespace std; 15 16 int gi() 17 { 18 int x=0,flag=1; 19 char ch=getchar(); 20 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) flag=-1;ch=getchar();} 21 while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar(); 22 return x*flag; 23 } 24 25 int fa[N],c[N][2],lazy[N],w[N],rev[N],st[N],siz[N],f[N]; 26 long long ans[N]; 27 28 struct date{ 29 int r,z,i,x; 30 bool operator < (const date a) const { 31 return r<a.r; 32 } 33 }qu[N]; 34 35 int isroot(int x){ 36 return c[fa[x]][0]!=x && c[fa[x]][1]!=x; 37 } 38 39 void pushdown(int x){ 40 if (lazy[x]){ 41 w[c[x][0]]+=lazy[x]*siz[c[x][0]],f[c[x][0]]+=lazy[x]; 42 w[c[x][1]]+=lazy[x]*siz[c[x][1]],f[c[x][1]]+=lazy[x]; 43 lazy[c[x][0]]+=lazy[x],lazy[c[x][1]]+=lazy[x]; 44 lazy[x]=0; 45 } 46 if (rev[x]==0) return; 47 rev[x]^=1,rev[c[x][0]]^=1,rev[c[x][1]]^=1; 48 swap(c[x][0],c[x][1]); 49 return; 50 } 51 52 void update(int x){ 53 siz[x]=siz[c[x][0]]+siz[c[x][1]]+1; 54 w[x]=w[c[x][0]]+w[c[x][1]]+f[x]; 55 return; 56 } 57 58 void rotate(int x){ 59 int y=fa[x],z=fa[y],l,r; 60 if (c[y][0]==x) l=0; 61 else l=1;r=l^1; 62 if (!isroot(y)) 63 if (c[z][0]==y) c[z][0]=x; 64 else c[z][1]=x; 65 fa[c[x][r]]=y,fa[y]=x,fa[x]=z; 66 c[y][l]=c[x][r],c[x][r]=y; 67 update(y),update(x); 68 return; 69 } 70 71 void splay(int x){ 72 int tot=0;st[++tot]=x; 73 for (RG int i=x; !isroot(i); i=fa[i]) st[++tot]=fa[i]; 74 for (RG int i=tot; i; --i) pushdown(st[i]); 75 while(!isroot(x)){ 76 int y=fa[x],z=fa[y]; 77 if (!isroot(y)) 78 if (c[y][0]==x ^ c[z][0]==y) rotate(x); 79 else rotate(y); 80 rotate(x); 81 } 82 return; 83 } 84 85 void access(int x){ 86 int t=0; 87 while(x){ 88 splay(x); 89 c[x][1]=t;update(x); 90 t=x,x=fa[x]; 91 } 92 } 93 94 void rever(int x){ 95 access(x),splay(x),rev[x]^=1; 96 return; 97 } 98 99 main(){ 100 freopen("lct.in","r",stdin); 101 freopen("lct.out","w",stdout); 102 int n=gi(),q=gi(),head=1; 103 siz[1]=1; 104 for (RG int i=2; i<=n; ++i) fa[i]=gi()+1,siz[i]=1; 105 for (RG int i=1; i<=q; ++i){ 106 int l=gi(),r=gi()+1,z=gi()+1; 107 qu[i]=(date){l,z,i,-1}; 108 qu[i+q]=(date){r,z,i,1}; 109 } 110 sort(qu+1,qu+2*q+1);q*=2; 111 for (RG int i=1; i<=n; ++i){ 112 rever(1),access(i),splay(i); 113 ++lazy[i],++f[i],w[i]+=siz[i]; 114 while(qu[head].r<=i && head<=q){ 115 int z=qu[head].z; 116 rever(1),access(z),splay(z); 117 update(z); 118 ans[qu[head].i]+=w[qu[head].z]*qu[head].x; 119 ++head; 120 } 121 } 122 q/=2; 123 for (RG int i=1; i<=q; ++i) printf("%lld\n",(ans[i]+mod)%mod); 124 return 0; 125 }
原文:http://www.cnblogs.com/cjk2001/p/6489844.html