题面
题解
前言
题意很好理解,注意深度和我们平常理解的深度相比还要加一。
首先暴力的方法肯定是直接枚举求两个点的 \(LCA\) 的深度,复杂度是 \(O(mnlogn)\)。
考虑对暴力的优化,用 \(tarjan\) 离线求,然后 \(O(1)\) 查。但是时空间都不允许。
于是我们必须另想做法。
LCA的深度
我们想想上述的暴力算法都停留在给每对点找 \(LCA\) 的过程中。时间也就浪费在这里,那么我们是否有更高效的算法去找一个区间的点到一个定点的 \(LCA\) 的深度呢。仔细读这句话,发现问题的重点其实是找深度,而不是找 \(LCA\) 。进而我们可以发现,\(LCA\) 的深度可以转化为两个点到根节点的路径的公共部分的长度。而这可以扩展到找多个点与一个点的 \(LCA\) 的深度之和。
发现找和的话,只用把这些公共的长度加起来,因为它们之间是不会相互影响的,这些都能用树链剖分很好的维护。
具体维护方法
- 区间修改 \(l - 1\) ~ \(r\) 将它们到根节点的路径上的点权都加一。
- 区间求和 \(l - 1\) 和 \(r\) 用 \(r\) 的答案减去 \(l - 1\) 的答案,就是最终的答案。
- 不懂的话手推一下就懂了,应该不难理解。
于是我们解决了只有一个询问的情况。
差分
发现问题是和 \(n\) 同级别的,不把它的复杂度优化掉还是过不了此题。
区间求和问题我们可以试试差分能不能解决。
怎么才能让所有的询问互不干扰呢?
因此我们需要 \(r-(l - 1)\) 的公共路径长度中,只包含这个询问中的公共路径长度。也就是说,在 \(l - 1\) 到 \(r\) 之间,既不能多加,又不能多减。这句话可能说的不是特别清楚,可以结合下面的解释和样例理解一下,就很好理解。
我们可以把每个询问的 \(l - 1\) 和 \(r\) 分别储存起来,从小到大排序。让后用一个变量 \(now\) 表示从 \(1\) 到 \(now\) 的节点,都把到根节点的路径的权值加了一。
证明互不干扰
感性理解:
可以把这棵树想成一棵带权树,树上只保存了 \(1\) 到 \(now\) 的节点每次把到根节点的路径的权值加了一后的情形,除此之外,什么都没有。
而我们要求一个区间到与某个点的 \(LCA\) 的深度之和,只需要查一次当更新到 \(l - 1\),和 \(r\) 时,查询那个点到根节点的路径的权值之和再相减就行了。这两次可能都包含了 \(1\) ~ \(l - 1\) 的多余的权值,相减之后,就只剩余了正确的区间和的答案。
代码
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 5e4 + 5,mod = 201314;
int n,m,ans[N];
struct SegmentTree {
#define MAXN N << 2
int l[MAXN],r[MAXN],sum[MAXN],tag[MAXN];
void build(int p,int lf,int rg) {
l[p] = lf; r[p] = rg;
if(lf == rg) {
sum[p] = tag[p] = 0;
return ;
}
int mid = (lf + rg) >> 1;
build(p << 1,lf,mid);
build(p << 1 | 1,mid + 1,rg);
}
inline void pushdown(int p) {
if(!tag[p]) return ;
sum[p << 1] = (sum[p << 1] + 1ll * tag[p] * (r[p << 1] - l[p << 1] + 1)) % mod;
sum[p << 1 | 1] = (sum[p << 1 | 1] + 1ll * tag[p] * (r[p << 1 | 1] - l[p << 1 | 1] + 1)) % mod;
tag[p << 1] = (tag[p << 1] + tag[p]) % mod;
tag[p << 1 | 1] = (tag[p << 1 | 1] + tag[p]) % mod;
tag[p] = 0;
}
void add(int p,int L,int R,int k) {
if(L <= l[p] && r[p] <= R) {
sum[p] = (sum[p] + k * (r[p] - l[p] + 1)) % mod;
tag[p] = (tag[p] + k) % mod;
return ;
}
int mid = (l[p] + r[p]) >> 1; pushdown(p);
if(L <= mid) add(p << 1,L,R,k);
if(R > mid) add(p << 1 | 1,L,R,k);
sum[p] = (sum[p << 1] + sum[p << 1 | 1]) % mod;
}
int query(int p,int L,int R) {
if(L <= l[p] && r[p] <= R) return sum[p];
int mid = (l[p] + r[p]) >> 1;
pushdown(p); int ans = 0;
if(L <= mid) ans = (ans + query(p << 1,L,R)) % mod;
if(R > mid) ans = (ans + query(p << 1 | 1,L,R)) % mod;
return ans;
}
}tr;
struct tree {
#define M N << 1
int head[N],next[M],to[M],size;
inline void add(int u,int v) {
next[++size] = head[u];
to[size] = v; head[u] = size;
next[++size] = head[v];
to[size] = u; head[v] = size;
}
int dep[N],fa[N],siz[N],son[N];
void dfs1(int x,int f,int deep) {
fa[x] = f; dep[x] = deep;
siz[x] = 1; int maxson = -1;
for(int i = head[x]; i; i = next[i]) {
int y = to[i];
if(y == f) continue;
dfs1(y,x,deep + 1);
siz[x] += siz[y];
if(siz[y] > maxson) son[x] = y,maxson = siz[y];
}
}
int id[N],dfn[N],top[N],cnt;
tree () {
cnt = 0;
}
void dfs2(int x,int topf) {
id[x] = ++cnt; top[x] = topf;
if(!son[x]) return;
dfs2(son[x],topf);
for(int i = head[x]; i; i = next[i]) {
int y = to[i];
if(y == fa[x] || y == son[x]) continue;
dfs2(y,y);
}
}
int q_sum(int x,int y,int ans = 0) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x,y);
ans = (ans + tr.query(1,id[top[x]],id[x])) % mod;
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x,y);
ans = (ans + tr.query(1,id[x],id[y])) % mod;
return ans;
}
void modify(int x,int y,int k = 1) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x,y);
tr.add(1,id[top[x]],id[x],k);
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x,y);
tr.add(1,id[x],id[y],k);
}
}a;
struct question {
int id,r,v,is;
bool operator < (const question &x) const {
return r < x.r;
}
}q[M];
inline int read() {
int x = 0,flag = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')flag = -1;ch = getchar();}
while(ch >='0' && ch <='9'){x = (x << 3) + (x << 1) + ch - 48;ch = getchar();}
return x * flag;
}
#include<iostream>
int main() {
n = read(),m = read(); a.size = 1;
for(int i = 2; i <= n; i++) {
int u = read() + 1;
a.add(u,i);
}
a.dfs1(1,0,0); a.dfs2(1,1);
tr.build(1,1,n); int len = 0;
for(int i = 1; i <= m; i++) {
int l = read();
int r = read() + 1;
int v = read() + 1;
q[++len] = (question) {i,l,v,-1};
q[++len] = (question) {i,r,v,1};
}
sort(q + 1,q + 1 + len); int now = 0;
for(int i = 1; i <= len; i++) {
while(now < q[i].r) a.modify(1,++now);
ans[q[i].id] += a.q_sum(1,q[i].v) * q[i].is;
}
for(int i = 1; i <= m; i++) printf("%d\n",(ans[i] + mod) % mod);
return 0;
}
© 著作权归作者所有
发表评论