【做题记录】P4211 [LNOI2014]LCA
P4211 [LNOI2014]LCA
题意
给出一个 \(n\) 个节点的有根树（编号为 \(0\) 到 \(n-1\)，根节点为 \(0\)）。
一个点的深度定义为这个节点到根的距离 \(+1\)。
设 \(dep[i]\) 表示点 \(i\) 的深度，\(LCA(i,j)\) 表示 \(i\) 与 \(j\) 的最近公共祖先。
有 \(m\) 次询问，每次询问给出 l r z，求 \(\sum_{i=l}^r dep[LCA(i,z)]\)。
题解
我们考虑这样一件事情，就是说，两个点的 \(Lca\) 的深度的意义到底是什么，如何才能够快速求的？
在我们不会求 \(Lca\) 的时候，我们会将一个点一个一个往上爬，并将路径上的点染色。之后我们将另一个点暴力往上跳，第一个染色过的点就是 \(Lca\)。
我们考虑到这样一件事情，如果我们将一个点到根的路径上每个点数值加 \(1\)，再求得另一个点到根的路径上的权值和，这不就是 \(Lca\) 的深度了吗？
于是求解一次询问就相当于对于 \(l\le x\le r\)，将 \(x\) 到根的路径上每个点加一，最后答案就是 \(z\) 到根的权值和。
由于询问次数很多，不可能每次都这样处理一遍，考虑将询问拆开。
\[\sum_{i=l}^r dep[LCA(i,z)]=\sum_{i=1}^r dep[LCA(i,z)]-\sum_{i=1}^{l-1} dep[LCA(i,z)] \]这样我们就可以在 \(O(n\log n)\) 复杂度内解决问题啦！
这就叫数据结构二步曲，学习一下，代码我现在放下。
#define Maxn 50005
#define pb push_back
#define mod 201314
typedef long long ll;
int n,m,tot,Time,cnt;
int ans[Maxn];
int dfn[Maxn],tp[Maxn],fa[Maxn],dep[Maxn],siz[Maxn],bigson[Maxn];
int hea[Maxn],nex[Maxn],ver[Maxn];
struct TREE { int laz,sum; }tree[Maxn<<2];
struct Query { int num,z,opt; };
vector q[Maxn];
void dfs1(int x)
{
siz[x]=1;
for(int i=hea[x];i;i=nex[i])
{
fa[ver[i]]=x,dep[ver[i]]=dep[x]+1;
dfs1(ver[i]),siz[x]+=siz[ver[i]];
if(siz[ver[i]]>siz[bigson[x]]) bigson[x]=ver[i];
}
}
void dfs2(int x,int T)
{
tp[x]=T,dfn[x]=++Time;
if(bigson[x]) dfs2(bigson[x],T);
for(int i=hea[x];i;i=nex[i])
{
if(ver[i]==bigson[x]) continue;
dfs2(ver[i],ver[i]);
}
}
void pushdown(int p,int nl,int nr)
{
int mid=(nl+nr)>>1;
tree[p<<1].laz=(tree[p<<1].laz+tree[p].laz)%mod;
tree[p<<1|1].laz=(tree[p<<1|1].laz+tree[p].laz)%mod;
tree[p<<1].sum=(tree[p<<1].sum+1ll*tree[p].laz*(mid-nl+1)%mod)%mod;
tree[p<<1|1].sum=(tree[p<<1|1].sum+1ll*tree[p].laz*(nr-mid)%mod)%mod;
tree[p].laz=0;
}
void add(int p,int nl,int nr,int l,int r)
{
if(nl>=l && nr<=r) { tree[p].laz++,tree[p].sum+=(nr-nl+1); return; }
pushdown(p,nl,nr);
int mid=(nl+nr)>>1;
if(mid>=l) add(p<<1,nl,mid,l,r);
if(mid=l && nr<=r) return tree[p].sum;
pushdown(p,nl,nr);
int mid=(nl+nr)>>1,ret=0;
if(mid>=l) ret=(ret+query(p<<1,nl,mid,l,r))%mod;
if(mid