P4427 [BJOI2018] 求和
（以下記每個點的點權為它在此題中的深度）
（以下運算均忽略取模）
我曾經聽說過一個技巧：對于有關樹上路徑的一類問題，我們可以把 \(u -> v\) 的路徑拆成 \(u->LCA\) 和 \(v->son_{LCA}\) 兩條鏈，其中 \(LCA\) 是 \(u,v\) 的最近公共祖先，\(son_{LCA}\) 指的是 \(v\) 的祖先中是 \(LCA\) 的兒子的節點。
而且我們發現這樣拆的話，兩條鏈上的點權還是連續的。這意味著我們可以直接預處理出一個 \(qwq_{i,j}\) （別問為什么是這個名，因為前綴），表示 \(1^i+2^i+\cdots+j^i\) 的值。
這樣對于某組查詢 \((u,v,k)\)，我們假設 \(a=dep_{u},b=dep{v},c=dep_{LCA},d=dep_{fa_{LCA}}\)，這樣我們拆出來的第一條鏈的貢獻是 \(qwq_{k,a}-qwq_{k,d}\)，第二條鏈的貢獻就是 \(qwq_{k,b}-qwq_{k,c}\)，有點類似前綴和差分的思想。
該查詢的最終結果就是兩個貢獻相加。
然后我們發現這個題結束了。我們直接倍增求LCA（當然你怎么求都行，不做要求），然后根據上面式子求答案就是了。
時間復雜度 \(O(nk \log k + (n + m) \log n)\)。
代碼：
P4427
#include<bits/stdc++.h>
#define int long long
#define _(x,y) (((x-y)%mod+mod)%mod)
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(c<48){
if(c=='-') f=-1;
c=getchar();
}
while(c>47) x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
const int N=3e5+5;
const int mod=998244353;
int n,m,h[N],tot,dep[N],f[23][N],qwq[52][N];
struct sw{
int u,v,nxt;
}e[2*N];
inline void add(int u,int v){
e[++tot]={u,v,h[u]};h[u]=tot;
}
inline void dfs(int u,int fa){
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(v==fa) continue;
f[0][v]=u;
dep[v]=dep[u]+1;
dfs(v,u);
}
}
inline int qpow(int a,int b){//快速冪
int ans=1;
while(b){
if(b&1) ans=(ans*a)%mod;
a=(a*a)%mod,b>>=1;
}
return ans;
}
inline int lca(int x,int y){//求最近公共祖先
if(dep[x]<dep[y]){
swap(x,y);
}
for(int i=20;i>=0;i--){
if(dep[f[i][x]]>=dep[y]){
x=f[i][x];
}
}
if(x==y){
return y;
}
for(int i=20;i>=0;i--){
if(f[i][x]!=f[i][y]){
x=f[i][x],y=f[i][y];
}
}
return f[0][x];
}
signed main(){
n=read();
//qwq數組預處理
for(int i=1;i<=50;i++){
for(int j=0;j<n;j++){
qwq[i][j]=(qwq[i][j-1]+qpow(j,i))%mod;
//我是用快速冪推的qwq數組，當然也可以不用快速冪省個log
}
}
for(int i=1;i<n;i++){
int u=read(),v=read();
add(u,v);add(v,u);
}
//LCA&dep預處理
dfs(1,0);
for(int i=1;i<=20;i++){
for(int j=1;j<=n;j++){
f[i][j]=f[i-1][f[i-1][j]];
}
}
m=read();
for(int i=1;i<=m;i++){
int u=read(),v=read(),k=read();
int LCA=lca(u,v);
//_(x,y)詳見define
//u->LCA
int ans1=_(qwq[k][dep[u]],qwq[k][dep[f[0][LCA]]]);
//v->son[LCA]
int ans2=_(qwq[k][dep[v]],qwq[k][dep[LCA]]);
int ans=(ans1+ans2)%mod;
printf("%lld\n",ans);
}
return 0;
}
浙公網安備 33010602011771號