传送门
problem
给出一个
n
n
n 个节点的有根树（编号为
0
0
0 到
n
−
1
n-1
n−1，根节点为
0
0
0）。一个点的深度定义为这个节点到根的距离
+
1
+1
+1。
设
d
e
p
[
i
]
dep[i]
dep[i] 表示点
i
i
i 的深度，
LCA
(
i
,
j
)
\texttt{LCA}(i,j)
LCA(i,j) 表示
i
i
i 与
j
j
j 的最近公共祖先。
有
q
q
q 次询问，每次询问给出
l
r
z
l\; r\; z
lrz，求
∑
i
=
l
r
d
e
p
[
LCA
(
i
,
z
)
]
\sum\limits_{i=l}^rdep[\texttt{LCA}(i,z)]
i=l∑rdep[LCA(i,z)]。
数据范围：
n
,
q
≤
50000
n,q\le50000
n,q≤50000。
solution
对于一组询问
l
r
z
l\;r\;z
lrz，对于
∀
i
∈
[
l
,
r
]
\forall i\in[l,r]
∀i∈[l,r]，设
LCA
(
i
,
z
)
=
g
i
\texttt{LCA}(i,z)=g_i
LCA(i,z)=gi。
首先比较显然的是，所有的
g
i
g_i
gi 应该在
1
1
1 到
z
z
z 的路径上。考虑
d
e
p
[
g
i
]
dep[g_i]
dep[gi] 的含义是
1
1
1 到
g
i
g_i
gi 路径上的点数，于是对于
∀
i
∈
[
l
,
r
]
\forall i\in[l,r]
∀i∈[l,r]，我们对
1
1
1 到
g
i
g_i
gi 这条链加
1
1
1，询问答案的时候
1
1
1 到
z
z
z 的链和就是答案。
但是，我们貌似没办法快速找到所有的
g
i
g_i
gi，这时换个思路，直接在
1
1
1 到
i
i
i 这条链加
1
1
1，发现效果是一样的。
可是，对于每个询问都暴力加点、暴力清空的话，复杂度又上去了，怎么办呢？
我们把拆开，即
a
n
s
[
l
,
r
]
=
a
n
s
[
1
,
r
]
−
a
n
s
[
1
,
l
−
1
]
ans_{[l,r]}=ans_{[1,r]}-ans_{[1,l-1]}
ans[l,r]=ans[1,r]−ans[1,l−1] ，左端点都变成
1
1
1，然后按右端点从小到大的顺序加点。这样做的好处就是，不用每次询问完就清空线段树，可以在上一次的基础上完成此次询问。
时间复杂度
O
(
n
log
2
n
)
O(n\log ^2n)
O(nlog2n)。
code
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define N 50005
#define P 201314
using namespace std
;
int n
,q
,cnt
,tot
;
int dep
[N
],fa
[N
],son
[N
],Size
[N
],top
[N
],pos
[N
],ans
[N
],tag
[N
<<2],sum
[N
<<2];
struct query
{int id
,r
,z
,flag
;}Q
[N
<<1];
vector
<int>e
[N
];
bool operator<(const query
&p
,const query
&q
) {return p
.r
<q
.r
;}
int add(int x
,int y
) {return x
+y
>=P
?x
+y
-P
:x
+y
;}
int dec(int x
,int y
) {return x
-y
< 0?x
-y
+P
:x
-y
;}
int mul(int x
,int y
) {return 1ll*x
*y
%P
;}
void dfs1(int x
){
Size
[x
]=1;
for(int &to
:e
[x
]){
fa
[to
]=x
,dep
[to
]=dep
[x
]+1;
dfs1(to
),Size
[x
]+=Size
[to
];
if(Size
[son
[x
]]<Size
[to
]) son
[x
]=to
;
}
}
void dfs2(int x
,int tp
){
top
[x
]=tp
,pos
[x
]=++tot
;
if(son
[x
]) dfs2(son
[x
],tp
);
for(int &to
:e
[x
])
if(to
!=son
[x
]) dfs2(to
,to
);
}
void addit(int root
,int len
,int num
){
tag
[root
]=add(tag
[root
],num
);
sum
[root
]=add(sum
[root
],mul(num
,len
));
}
void pushdown(int root
,int l
,int r
,int mid
){
if(!tag
[root
]) return;
addit(root
<<1,mid
-l
+1,tag
[root
]);
addit(root
<<1|1,r
-mid
,tag
[root
]);
tag
[root
]=0;
}
#define mid ((l+r)>>1)
void Modify(int root
,int l
,int r
,int x
,int y
){
if(l
>=x
&&r
<=y
){
return addit(root
,r
-l
+1,1);
}
pushdown(root
,l
,r
,mid
);
if(x
<=mid
) Modify(root
<<1,l
,mid
,x
,y
);
if(y
> mid
) Modify(root
<<1|1,mid
+1,r
,x
,y
);
sum
[root
]=add(sum
[root
<<1],sum
[root
<<1|1]);
}
int Query(int root
,int l
,int r
,int x
,int y
){
if(l
>=x
&&r
<=y
) return sum
[root
];
pushdown(root
,l
,r
,mid
);
if(y
<=mid
) return Query(root
<<1,l
,mid
,x
,y
);
if(x
> mid
) return Query(root
<<1|1,mid
+1,r
,x
,y
);
return add(Query(root
<<1,l
,mid
,x
,y
),Query(root
<<1|1,mid
+1,r
,x
,y
));
}
#undef mid
void Add(int x
){
while(top
[x
]!=1){
Modify(1,1,n
,pos
[top
[x
]],pos
[x
]),x
=fa
[top
[x
]];
}
Modify(1,1,n
,1,pos
[x
]);
}
int Ask(int x
){
int ans
=0;
while(top
[x
]!=1){
ans
=add(ans
,Query(1,1,n
,pos
[top
[x
]],pos
[x
])),x
=fa
[top
[x
]];
}
return add(ans
,Query(1,1,n
,1,pos
[x
]));
}
int main(){
scanf("%d%d",&n
,&q
);
for(int i
=2,x
;i
<=n
;++i
) scanf("%d",&x
),e
[x
+1].push_back(i
);
dep
[1]=1,dfs1(1),dfs2(1,1);
for(int i
=1,l
,r
,z
;i
<=q
;++i
){
scanf("%d%d%d",&l
,&r
,&z
);
Q
[++cnt
]=(query
){i
,l
,z
+1,0};
Q
[++cnt
]=(query
){i
,r
+1,z
+1,1};
}
sort(Q
+1,Q
+cnt
+1);
int now
=0;
for(int i
=1;i
<=cnt
;++i
){
while(now
<Q
[i
].r
) Add(++now
);
if(Q
[i
].flag
) ans
[Q
[i
].id
]=add(ans
[Q
[i
].id
],Ask(Q
[i
].z
));
else ans
[Q
[i
].id
]=dec(ans
[Q
[i
].id
],Ask(Q
[i
].z
));
}
for(int i
=1;i
<=q
;++i
) printf("%d\n",ans
[i
]);
return 0;
}
