题意
给一棵 \(n\) 个点，以 \(1\) 为根有根树和一个整数 \(k\)，\(q\) 组询问，每组给定 \(x,y\)，求：
\[\sum\limits_{i=1}^{x}\operatorname{depth}\left(\operatorname{lca}(x,y)\right)^k
\]
对 \(998244353\) 取模。
\(\texttt{Data Range:}1\leq n,q\leq 5\times 10^4,1\leq k\leq 10^9\)
题解
首先看一个弱化版：[LNOI2014]LCA，先考虑这个题目怎么做。
注意到这里有一个很朴素的求 \(x,y\) 的 LCA 的方法：首先先将 \(x\) 到根的路径上的所有点打个标记，然后 \(y\) 到根的路径中深度最大的点就是两个点的 LCA。
注意到在 \(y\) 到根的路径上，如果一个点被打了标记，那么这个点的所有祖先都会被打标记。所以说，\(x,y\) 的 LCA 的所有祖先都是被打标记的，而 \(y\) 到 LCA 的这一段都是没打标记的。
于是可以通过数一下 \(y\) 到根中被打标记点的个数得到 \(\operatorname{depth}\left(\operatorname{lca}(x,y)\right)\)。
在这个的基础之上，我们就有了一个方法：
对于所有满足 \(l\leq x\leq r\) 的 \(x\) 都将 \(x\) 到根的所有点点权加一，然后查询一下 \(z\) 到根的所有点的点权和即可。
但是这么做是 \(O(qn\log^2n)\) 的，很明显无法通过。
我们考虑对询问 \([l,r]\) 拆成 \([1,r]\) 和 \([1,l-1]\) 的形式。然后类似于莫队一样，因为所有询问的左端点都是一样的，所以可以先按照右端点排序，用一个指针扫一下即可，复杂度 \(O(n\log^2n)\)。
现在考虑这个题，瓶颈是看能不能有一个普适性的方法来求出 \(\operatorname{depth}\left(\operatorname{lca}(x,y)\right)^k\)。
注意到我们可以对这个东西进行差分。设 \(w_x=\operatorname{depth}(x)^k-\operatorname{depth}\left(fa_x\right)^k\)，那么根到 \(x\) 路径上的 \(w_x\) 之和恰好就是 \(\operatorname{depth}(x)^k\)！
于是还是按照原来一样，将所有询问按照右端点排序（因为左端点都为 \(1\)），然后用一个指针扫一遍所有询问即可。
但是会出现一个问题，就是需要对于所有 \(l\leq i\leq r\) 的 位置 \(i\) 加 \(w_i\)。
这里大多数题解都没讲清楚。考虑记一个 \(v_i\) 在树剖求出的 dfn 的前缀和 \(w_i\)。然后如果递归到某个被询问区间包含的线段树区间 \([l,r]\)，将这一段区间的和加上一个 \(w_r-w_{l-1}\)，然后打标记。
对于标记下传的话也是差不多的，然后这道题就解决了，具体实现可以看代码。
代码
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=2e5+51,MOD=998244353;
struct Edge{
ll to,prev;
};
struct SegmentTree{
ll l,r,sm,tag;
};
struct Query{
ll r,u,id;
inline bool operator <(const Query &rhs)const
{
return this->r<rhs.r;
}
};
Edge ed[MAXN<<1];
SegmentTree tree[MAXN<<2];
Query qry[MAXN];
ll n,qcnt,kk,to,tot,totd,r,u,lst;
ll last[MAXN],fa[MAXN],depth[MAXN],sz[MAXN],hv[MAXN],dfn[MAXN];
ll top[MAXN],w[MAXN],v[MAXN],pw[MAXN],res[MAXN],rdfn[MAXN];
inline ll read()
{
register ll num=0,neg=1;
register char ch=getchar();
while(!isdigit(ch)&&ch!='-')
{
ch=getchar();
}
if(ch=='-')
{
neg=-1;
ch=getchar();
}
while(isdigit(ch))
{
num=(num<<3)+(num<<1)+(ch-'0');
ch=getchar();
}
return num*neg;
}
inline ll qpow(ll base,ll exponent)
{
ll res=1;
while(exponent)
{
if(exponent&1)
{
res=(li)res*base%MOD;
}
base=(li)base*base%MOD,exponent>>=1;
}
return res;
}
inline void addEdge(ll from,ll to)
{
ed[++tot].prev=last[from];
ed[tot].to=to;
last[from]=tot;
}
inline void dfs(ll node,ll f)
{
ll mx=-1;
sz[node]=1,pw[node]=qpow(depth[node]=depth[fa[node]=f]+1,kk);
for(register int i=last[node];i;i=ed[i].prev)
{
if(ed[i].to!=f)
{
dfs(ed[i].to,node),sz[node]+=sz[ed[i].to];
sz[ed[i].to]>mx?mx=sz[hv[node]=ed[i].to]:1;
}
}
}
inline void dfs2(ll node,ll link)
{
ll to;
rdfn[dfn[node]=++totd]=node,top[node]=link;
if(!hv[node])
{
return;
}
dfs2(hv[node],link);
for(register int i=last[node];i;i=ed[i].prev)
{
(to=ed[i].to)!=fa[node]&&to!=hv[node]?dfs2(to,to):(void)1;
}
}
#define ls node<<1
#define rs (node<<1)|1
inline void update(ll node)
{
tree[node].sm=(tree[ls].sm+tree[rs].sm)%MOD;
}
inline void create(ll l,ll r,ll node)
{
tree[node]=(SegmentTree){l,r,0,0};
if(l==r)
{
return;
}
ll mid=(l+r)>>1;
create(l,mid,ls),create(mid+1,r,rs),update(node);
}
inline void spread(ll node)
{
if(tree[node].tag)
{
ll tag=tree[node].tag;
tree[ls].sm+=(li)tag*(v[tree[ls].r]-v[tree[ls].l-1]+MOD)%MOD;
tree[rs].sm+=(li)tag*(v[tree[rs].r]-v[tree[rs].l-1]+MOD)%MOD;
tree[ls].sm%=MOD,tree[rs].sm%=MOD;
tree[ls].tag+=tag,tree[rs].tag+=tag,tree[node].tag=0;
}
}
inline void add(ll l,ll r,ll node)
{
if(l<=tree[node].l&&r>=tree[node].r)
{
tree[node].sm+=(v[tree[node].r]-v[tree[node].l-1]+MOD)%MOD;
return (void)(tree[node].sm%=MOD,tree[node].tag++);
}
ll mid=(tree[node].l+tree[node].r)>>1;
spread(node);
l<=mid?add(l,r,ls):(void)1,r>mid?add(l,r,rs):(void)1,update(node);
}
inline ll query(ll l,ll r,ll node)
{
if(l<=tree[node].l&&r>=tree[node].r)
{
return tree[node].sm;
}
ll mid=(tree[node].l+tree[node].r)>>1;
spread(node);
return ((l<=mid?query(l,r,ls):0)+(r>mid?query(l,r,rs):0))%MOD;
}
inline void add(ll x,ll y)
{
while(top[x]!=top[y])
{
depth[top[x]]<depth[top[y]]?swap(x,y):(void)1;
add(dfn[top[x]],dfn[x],1),x=fa[top[x]];
}
depth[x]>depth[y]?swap(x,y):(void)1;
add(dfn[x],dfn[y],1);
}
inline ll query(ll x,ll y)
{
ll res=0;
while(top[x]!=top[y])
{
depth[top[x]]<depth[top[y]]?swap(x,y):(void)1;
res=(res+query(dfn[top[x]],dfn[x],1))%MOD,x=fa[top[x]];
}
depth[x]>depth[y]?swap(x,y):(void)1;
return (res+query(dfn[x],dfn[y],1))%MOD;
}
int main()
{
n=read(),qcnt=read(),kk=read();
for(register int i=2;i<=n;i++)
{
to=read(),addEdge(i,to),addEdge(to,i);
}
for(register int i=1;i<=qcnt;i++)
{
r=read(),u=read(),qry[i]=(Query){r,u,i};
}
dfs(1,0),dfs2(1,1),create(1,n,1);
for(register int i=1;i<=n;i++)
{
w[i]=(pw[i]-pw[fa[i]]+MOD)%MOD;
}
for(register int i=1;i<=n;i++)
{
v[i]=(v[i-1]+w[rdfn[i]])%MOD;
}
sort(qry,qry+qcnt+1);
for(register int i=1;i<=qcnt;i++)
{
for(register int j=lst+1;j<=qry[i].r;j++)
{
add(1,j);
}
lst=qry[i].r,res[qry[i].id]=query(1,qry[i].u);
}
for(register int i=1;i<=qcnt;i++)
{
printf("%d\n",res[i]);
}
}
