本文共 2913 字，大约阅读时间需要 9 分钟。

题目大意： 给出一棵树和多个询问，以及一个常数 $k$，每次询问给出 $x,y$，求 ${\sum }_{i=1}^{x}dep(lca(i,y){)}^k$。

题解

当 $k=1$ 时，就是。

类似的，我们也将一个 $x$ 的贡献放到 $1$ 到 $x$ 的路径上，考虑每个点的权值。

观察 $k=1$ 时，此时深度 $+1$ 带来的贡献是 $(deep[x]+1{)}^k-deep[x{]}^k=1$，同样的，当 $k\ne 1$ 时，也是这个贡献。

对于每个点再维护一个 $s[i]$，对于每个节点 $x$，让 $1$ 到 $x$ 路径上的点的 $s[i]+1$，那么每个节点的贡献就是 $s[x]\times$ 上面那一串。

这个也用树剖就能维护，不过要用线段树维护重链上的数据而不能用树状数组。

代码如下：

#include 
   
    #include 
    
     #include 
     
      using namespace std;#define maxn 100010#define mod 998244353int n,q,k;struct edge{
   int y,next;}e[maxn];int first[maxn],len=0;void buildroad(int x,int y){
   e[++len]=(edge){
   y,first[x]};first[x]=len;}int fa[maxn],size[maxn],mson[maxn],deep[maxn];void dfs1(int x,int dep){
   	size[x]=1;deep[x]=dep;	for(int i=first[x];i;i=e[i].next)	{
   		int y=e[i].y;if(y==fa[x])continue;		fa[y]=x;dfs1(y,dep+1);size[x]+=size[y];		if(size[y]>size[mson[x]])mson[x]=y;	}}int id[maxn],tot=0,old[maxn],top[maxn];void dfs2(int x,int tp){
   	id[x]=++tot;old[tot]=x;top[x]=tp;	if(mson[x])dfs2(mson[x],tp);	for(int i=first[x];i;i=e[i].next)	if(e[i].y!=fa[x]&&e[i].y!=mson[x])dfs2(e[i].y,e[i].y);}int ksm(int x,int y){
   int re=1;for(;(y&1?re=1ll*re*x%mod:0),y;y>>=1,x=1ll*x*x%mod);return re;}int add(int &x,int y){
   x=(x+y>=mod?x+y-mod:x+y);}struct node{
   	int l,r,mid,val,sum,lazy;node *zuo,*you;	node(int x,int y):l(x),r(y),mid(l+r>>1),sum(0),lazy(0){
   		if(x
      
       val+you->val)%mod;		else zuo=you=NULL,val=(ksm(deep[old[l]],k)-ksm(deep[old[l]]-1,k)+mod)%mod;	}	void pushdown(){
   		if(lazy){
   			if(zuo)add(zuo->sum,1ll*zuo->val*lazy%mod),add(you->sum,1ll*you->val*lazy%mod),			zuo->lazy+=lazy,you->lazy+=lazy; lazy=0;		}	}	void change(int x,int y)	{
   		pushdown();if(l==x&&r==y){
   add(sum,val);lazy++;return;}		if(y<=mid)zuo->change(x,y);else if(x>=mid+1)you->change(x,y);		else zuo->change(x,mid),you->change(mid+1,y);sum=(zuo->sum+you->sum)%mod;	}	int getsum(int x,int y)	{
   		pushdown();if(l==x&&r==y)return sum;		if(y<=mid)return zuo->getsum(x,y);		else if(x>=mid+1)return you->getsum(x,y);		else return (zuo->getsum(x,mid)+you->getsum(mid+1,y))%mod;	}}*root;struct que{
   int x,y,pos;}ask[maxn];bool cmp(que x,que y){
   return x.x
       
        change(id[top[x]],id[x]),x=fa[top[x]];}int go2(int x){
   int re=0;while(x)add(re,root->getsum(id[top[x]],id[x])),x=fa[top[x]];return re;}int main(){
   	scanf("%d %d %d",&n,&q,&k);for(int i=2,x;i<=n;i++)	scanf("%d",&x),buildroad(x,i); dfs1(1,1); dfs2(1,1); root=new node(1,n);	for(int i=1;i<=q;i++)scanf("%d %d",&ask[i].x,&ask[i].y),ask[i].pos=i;	sort(ask+1,ask+q+1,cmp);int now=1;for(int i=1;i<=q;i++){
   		while(now<=ask[i].x)go1(now),now++;		ans[ask[i].pos]=go2(ask[i].y);	}	for(int i=1;i<=q;i++)printf("%d\n",ans[i]);}
       
      
     
    
   

转载地址：http://lsnib.baihongyu.com/