目录
显示
题面链接
https://www.luogu.com.cn/problem/P4211
题解
考虑最原始的 LCA 求法：我们从两个点出发，向上爬，并标记沿途所有节点。所有被标记两次的点中最深的点就是这两个点的 LCA。
仿照这样的思路，我们可以很快想出一种求 LCA 深度的方法：将一个点到根节点路径上的所有点的权值标记为 \(1\)，则另外一个点到根节点路径上的点权和即为这两个点 LCA 的深度。
于是我们有了一种 \(O(qn \log^2 n)\) 时间复杂度的算法：对于每个的询问，将 \([l,r]\) 内的每个点到根节点路径上的所有点的权值加一，则 \(z\) 到根节点路径上的权值和即为所求。
然而这个算法还是太慢了。原因是我们每次查询都需要重新初始化整棵树，做了很多重复的工作。如果能确保每个点到根节点的路径只执行一次修改操作的话，就可以在 \(O(n \log^2 n)\) 的时间复杂度内解决问题了。
我们可以利用差分的技巧：区间 \([l,r]\) 的答案可以由 \([1,r]\) 的答案减去 \([1,l-1]\) 的答案得到。因此我们可以按上面的方法将每个询问拆分成两个区间，按右端点排序，每处理一个询问时就将要用到的点添加进去，并计算答案。
到此，问题得到了完美解决。
#include <cstdio>
#include <vector>
#include <algorithm>
#define MOD 201314
using namespace std;
struct query
{
int l,r,z,id,op;
bool operator<(const query&a)const
{
return r<a.r||(r==a.r&&l<a.l);
}
};
struct seg
{
int sum,tag;
}s[200005];
struct edge
{
int v,next;
}e[50005];
vector<query> q;
int n,Q;
int head[50005],ans[50005];
int siz[50005],dep[50005],son[50005],fa[50005];
int id[50005],top[50005],cnt;
void addedge(int u,int v)
{
e[++cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs1(int u,int f)
{
siz[u]=1;
dep[u]=dep[f]+1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int t)
{
id[u]=++cnt;
top[u]=t;
if(!son[u])return;
dfs2(son[u],t);
for(int i=head[u];i;i=e[i].next)
if(e[i].v!=son[u])dfs2(e[i].v,e[i].v);
}
void pushup(int root)
{
s[root].sum=(s[root<<1].sum+s[root<<1|1].sum)%MOD;
}
void pushdown(int root,int l,int r)
{
int mid=(l+r)>>1;
s[root<<1].tag+=s[root].tag;s[root<<1].tag%=MOD;
s[root<<1|1].tag+=s[root].tag;s[root<<1|1].tag%=MOD;
s[root<<1].sum+=s[root].tag*(mid-l+1);s[root<<1].sum%=MOD;
s[root<<1|1].sum+=s[root].tag*(r-mid);s[root<<1|1].sum%=MOD;
s[root].tag=0;
}
void update(int root,int cl,int cr,int l,int r,int x)
{
if(r<cl||cr<l)return;
if(l<=cl&&cr<=r)
{
s[root].tag+=x;
s[root].sum=(s[root].sum+(cr-cl+1)*x)%MOD;
return;
}
pushdown(root,cl,cr);
int mid=(cl+cr)>>1;
update(root<<1,cl,mid,l,r,x);
update(root<<1|1,mid+1,cr,l,r,x);
pushup(root);
}
int query(int root,int cl,int cr,int l,int r)
{
if(r<cl||cr<l)return 0;
if(l<=cl&&cr<=r)return s[root].sum;
pushdown(root,cl,cr);
int mid=(cl+cr)>>1;
return (query(root<<1,cl,mid,l,r)+query(root<<1|1,mid+1,cr,l,r))%MOD;
}
void update_chain(int x,int y,int z)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,1,n,id[top[x]],id[x],z);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
update(1,1,n,id[x],id[y],z);
}
int query_chain(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=(ans+query(1,1,n,id[top[x]],id[x]))%MOD;
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ans=(ans+query(1,1,n,id[x],id[y]))%MOD;
return ans;
}
int main()
{
scanf("%d%d",&n,&Q);
for(int i=2;i<=n;i++)
{
scanf("%d",&fa[i]);
fa[i]++;
addedge(fa[i],i);
}
cnt=0;
dfs1(1,1);
dfs2(1,1);
for(int i=1;i<=Q;i++)
{
int l,r,z;
scanf("%d%d%d",&l,&r,&z);
l++,r++,z++;
q.push_back({l,r,z,i,1});
q.push_back({1,l-1,z,i,-1});
}
sort(q.begin(),q.end());
int u=1;
for(auto i:q)
{
while(u<=i.r)
{
update_chain(1,u,1);
u++;
}
ans[i.id]+=i.op*query_chain(1,i.z);
}
for(int i=1;i<=Q;i++)
printf("%d\n",(ans[i]%MOD+MOD)%MOD);
return 0;
}