master 对树上的求和非常感兴趣。
他生成了一棵有根树,并且希望多次询问这棵树上一段路径上所有节点深度的k 次方和,而且每次的k 可能是不同的。
此处节点深度的定义是这个节点到根的路径上的边数。
他把这个问题交给了pupil,但pupil 并不会这么复杂的操作,你能帮他解决吗?
for(int i=1;i<=50;i++)val[rt][i]=(val[fa[rt]][i]+mexp(deep[rt]-1,i))%MOD;
每次询问就这样:
long long ans=((val[x][k]-val[lca][k]+MOD)%MOD+(val[y][k]-val[fa[lca]][k]+MOD)%MOD)%MOD;
记得取模会有负数。。。
总复杂度的话就是$O(nk\log_2k+m\log_2n)$。
话说$BJOI$怎么$T1$这么简单,送分题啊。。。
跟$HNOI/AHOI$完全不能比啊。。。
附代码:
#include<iostream> #include<algorithm> #include<cstdio> #define MAXN 300010 #define MOD 998244353LL using namespace std; int n,m,c=1; int head[MAXN],deep[MAXN],son[MAXN],size[MAXN],fa[MAXN],top[MAXN]; long long val[MAXN][55]; struct Tree{ int next,to; }a[MAXN<<1]; inline int read(){ int date=0,w=1;char c=0; while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();} return date*w; } long long mexp(long long a,long long b){ long long s=1; while(b){ if(b&1)s=s*a%MOD; a=a*a%MOD; b>>=1; } return s%MOD; } inline void add(int x,int y){ a[c].to=y;a[c].next=head[x];head[x]=c++; a[c].to=x;a[c].next=head[y];head[y]=c++; } void dfs1(int rt){ son[rt]=0;size[rt]=1; for(int i=1;i<=50;i++)val[rt][i]=(val[fa[rt]][i]+mexp(deep[rt]-1,i))%MOD; for(int i=head[rt];i;i=a[i].next){ int will=a[i].to; if(!deep[will]){ deep[will]=deep[rt]+1; fa[will]=rt; dfs1(will); size[rt]+=size[will]; if(size[will]>size[son[rt]])son[rt]=will; } } } void dfs2(int rt,int f){ top[rt]=f; if(son[rt])dfs2(son[rt],f); for(int i=head[rt];i;i=a[i].next){ int will=a[i].to; if(will!=fa[rt]&&will!=son[rt])dfs2(will,will); } } int LCA(int x,int y){ while(top[x]!=top[y]){ if(deep[top[x]]<deep[top[y]])swap(x,y); x=fa[top[x]]; } if(deep[x]>deep[y])swap(x,y); return x; } void work(){ int x,y,k; while(m--){ x=read();y=read();k=read(); int lca=LCA(x,y); long long ans=((val[x][k]-val[lca][k]+MOD)%MOD+(val[y][k]-val[fa[lca]][k]+MOD)%MOD)%MOD; printf("%lld\n",ans); } } void init(){ int x,y; n=read(); for(int i=1;i<n;i++){ x=read();y=read(); add(x,y); } m=read(); deep[1]=1; dfs1(1); dfs2(1,1); } int main(){ init(); work(); return 0; }
原文:https://www.cnblogs.com/Yangrui-Blog/p/9466903.html