题解 P4211 【[LNOI2014]LCA】

感谢hzwer大佬的博客指示...... 可以发现，问题能够转化为从询问点到根都加1，然后询问l到r的点到根的路径上权值之和。然后这个问题又和“l到r的点到根路径上所有点权值分别+1，求询问点到根路径上的权值之和”等价。 然后就可做了。将询问差分一下，变成查询$[1,r]-[1,l-1]$。这时候只需要离线询问，在l-1和r处分别打标记，在从1~n依次遍历，扫到标记就查询，用树链剖分套线段树维护。最后将答案全部输出即可。时间复杂度$O(n\log_2^2n)$。 代码：(笔记本打的，缩进有点丑) ```cpp #include<bits/stdc++.h> #define For(i,a,b) for(i=(a);i<=(b);++i) #define Forward(i,a,b) for(i=(a);i>=(b);--i) #define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i) #define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i) using namespace std; template<typename T>inline void read(T &x) { T s=0,f=1;char k=getchar(); while(!isdigit(k)&&(k^'-'))k=getchar(); if(!isdigit(k)){f=-1;k=getchar();} while(isdigit(k)){s=s*10+(k^48);k=getchar();} x=s*f; } void file() { #ifndef ONLINE_JUDGE freopen("test.in","r",stdin); freopen("test.out","w",stdout); #endif } #define Chkmax(a,b) a=a>(b)?a:(b) #define Chkmin(a,b) a=a<(b)?a:(b) const int MAXN=5e4+7; static struct edge { int v,nxt; }p[MAXN]; static int n,m,e,head[MAXN],dep[MAXN]; static int fa[MAXN],sz[MAXN],son[MAXN]; inline void add(int u,int v) {p[++e].v=v;p[e].nxt=head[u];head[u]=e;} void dfs(int u) { sz[u]=1;dep[u]=dep[fa[u]]+1; for(register int v=head[u];v;v=p[v].nxt) { dfs(p[v].v);sz[u]+=sz[p[v].v]; if(!son[u]||sz[p[v].v]>sz[son[u]]) son[u]=p[v].v; } } static int top[MAXN],dfn[MAXN],ri[MAXN]; void dfs(int u,int tp) { ri[dfn[u]=++e]=u;top[u]=tp; if(son[u])dfs(son[u],tp); else return; for(register int v=head[u];v;v=p[v].nxt) if(p[v].v^son[u])dfs(p[v].v,p[v].v); } const int mod=201314; static vector<int>pl[MAXN],mi[MAXN]; static int ask[MAXN]; inline void init() { read(n);read(m); Rep(i,2,n)read(fa[i]),add(++fa[i],i); dfs(1);e=0;dfs(1,1); static int l,r; Rep(i,1,m)read(l),read(r),read(ask[i]) ,mi[l].push_back(i),pl[r+1].push_back(i) ,++ask[i]; } static int sum[MAXN<<2],laz[MAXN<<2]; static int ans[MAXN]; inline void pushdown(int h,int l,int r) { if(laz[h]) { static int mid;mid=(l+r)>>1; sum[h<<1]=(sum[h<<1] +1ll*laz[h]*(mid-l+1)%mod)%mod; sum[h<<1|1]=(sum[h<<1|1] +1ll*laz[h]*(r-mid)%mod)%mod; laz[h<<1]+=laz[h];laz[h<<1|1]+=laz[h]; laz[h]=0; } } void modify(int h,int l,int r,int x,int y) { if(l>=x&&r<=y) { sum[h]=(sum[h]+r-l+1)%mod; ++laz[h];return; } pushdown(h,l,r); int mid=(l+r)>>1; if(x<=mid)modify(h<<1,l,mid,x,y); if(y>mid)modify(h<<1|1,mid+1,r,x,y); sum[h]=(sum[h<<1]+sum[h<<1|1])%mod; } inline void modi(int x) { while(x) { modify(1,1,n,dfn[top[x]],dfn[x]) ,x=fa[top[x]];} } static vector<int>::iterator it; inline int query(int h,int l,int r,int x,int y) { if(l>=x&&r<=y)return sum[h]; pushdown(h,l,r); int mid=(l+r)>>1,ans=0; if(x<=mid)ans=query(h<<1,l,mid,x,y); if(y>mid)ans=(ans+query(h<<1|1,mid+1,r,x,y))%mod; return ans; } inline int qu(int x) { static int ans;ans=0; while(x) { ans=(ans+query(1,1,n,dfn[top[x]],dfn[x])); x=fa[top[x]]; } return ans; } inline void solve() { Rep(i,1,n) { modi(i); for(it=pl[i].begin();it!=pl[i].end();++it) ans[*it]+=qu(ask[*it]); for(it=mi[i].begin();it!=mi[i].end();++it) ans[*it]-=qu(ask[*it]); } Rep(i,1,m)printf("%d\n",(ans[i]%mod+mod)%mod); } int main() { file(); init(); solve(); return 0; } ``` ~~其实还能用LCT优化到$O(n\log_2n)$，但是太麻烦了......$~~