正題

題目大意:https://www.luogu.org/problem/P4427

---

題目大意

一棵樹，每次給一條路徑，求路徑上每個(gè)點(diǎn)的深度的$k$次方的和。

---

解題思路

路徑上分成兩條深度連續(xù)的鏈，所以我們可以先預(yù)處理出$k$次方的前綴和。

然后$LCA$就好了。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define S(l,r,k) ((sum[k][r]-sum[k][l-1]+XJQ)%XJQ) #define ll long long using namespace std; const ll N=310000,XJQ=998244353; struct node{ll to,next; }a[2*N]; ll n,m,tot,ls[N],dep[N],f[N][21],sum[51][N]; queue<int> q; void addl(ll x,ll y) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot; } void bfs() {q.push(1);dep[1]=1;while(!q.empty()){ll x=q.front();q.pop();for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(dep[y]) continue;dep[y]=dep[x]+1;f[y][0]=x;q.push(y);}}for(ll i=1;i<=20;i++)for(ll j=1;j<=n;j++)f[j][i]=f[f[j][i-1]][i-1]; } ll LCA(ll x,ll y,ll k) {ll X=dep[x]-1,Y=dep[y]-1;if(dep[x]<dep[y])swap(x,y);for(ll i=20;i>=0;i--)if(dep[f[x][i]]>=dep[y])x=f[x][i];if(x!=y){for(ll i=20;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];x=f[x][0];y=f[y][0];}return (S(dep[x]-1,X,k)+S(dep[y]-1,Y,k)-S(dep[x]-1,dep[x]-1,k)+XJQ)%XJQ; } int main() {scanf("%lld",&n);for(ll i=1;i<n;i++){ll x,y;scanf("%lld%lld",&x,&y);addl(x,y);addl(y,x);}for(ll i=1;i<=n;i++){sum[1][i]=i;for(ll j=2;j<=50;j++)sum[j][i]=sum[j-1][i]*i%XJQ;for(ll j=1;j<=50;j++)(sum[j][i]+=sum[j][i-1])%=XJQ; }scanf("%lld",&m);bfs();while(m--){ll x,y,k;scanf("%lld%lld%lld",&x,&y,&k);printf("%lld\n",LCA(x,y,k));} }

總結(jié)

以上是生活随笔為你收集整理的P4427-[BJOI2018]求和【LCA】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。