目录
显示
题面链接
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; }