正題

題目鏈接:https://www.luogu.com.cn/problem/P5305

---

題目大意

給一棵有根樹和$k$，$Q$次詢問給出$x,y$求
$$\sum _{i=1}^{x}de{p}_{LCA(i,y)}^k$$

$1\le n,Q\le 5\times 10^5,1\le k\le 10^9$

---

解題思路

和之前$LCA$那題一樣的思路，如果$k$等于$1$的話。加入一個點$i$就把$i$到根節點的路徑上加一，然后詢問節點$x$就查詢$x$到根節點路徑的和。

這題的話多了個$k$，其實是一樣的，只是每個點的權值要調成$de{p}_x^k?(de{p}_x?1{)}^k$，然后詢問路徑上權值*點權的和就好了。

因為$k$是固定的，所以直接開個線段樹就很好搞了。

時間復雜度$O(n{\log }^{2}n)$

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=5e5+10,P=998244353; struct node{ll to,next; }a[N]; struct qnode{ll l,x,id; }q[N]; ll n,Q,k,tot,pw[N],ls[N],fa[N],ans[N]; ll cnt,siz[N],dep[N],son[N],top[N],dfn[N],rfn[N]; ll w[N<<2],v[N<<2],lazy[N<<2]; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; } void addl(ll x,ll y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } bool cmp(qnode x,qnode y) {return x.l<y.l;} void dfs1(ll x){siz[x]=1;dep[x]=dep[fa[x]]+1;for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;dfs1(y);siz[x]+=siz[y];if(siz[y]>siz[son[x]])son[x]=y;}return; } void dfs2(ll x){dfn[++cnt]=x;rfn[x]=cnt;if(son[x]){top[son[x]]=top[x];dfs2(son[x]);}for(ll i=ls[x];i;i=a[i].next){ll y=a[i].to;if(y==son[x])continue;top[y]=y;dfs2(y);}return; } void Build(ll x,ll l,ll r){if(l==r){w[x]=(pw[dep[dfn[l]]]-pw[dep[dfn[l]]-1]+P)%P;return;}ll mid=(l+r)>>1;Build(x*2,l,mid);Build(x*2+1,mid+1,r);w[x]=(w[x*2]+w[x*2+1])%P;return; } void Downdata(ll x){if(!lazy[x])return;lazy[x*2]+=lazy[x];lazy[x*2+1]+=lazy[x];(v[x*2]+=w[x*2]*lazy[x]%P)%=P;(v[x*2+1]+=w[x*2+1]*lazy[x]%P)%=P;lazy[x]=0;return; } void Change(ll x,ll L,ll R,ll l,ll r){if(L==l&&R==r){lazy[x]++;(v[x]+=w[x])%=P;return;}ll mid=(L+R)>>1;Downdata(x);if(r<=mid)Change(x*2,L,mid,l,r);else if(l>mid)Change(x*2+1,mid+1,R,l,r);else Change(x*2,L,mid,l,mid),Change(x*2+1,mid+1,R,mid+1,r);v[x]=(v[x*2]+v[x*2+1])%P;return; } ll Ask(ll x,ll L,ll R,ll l,ll r){if(L==l&&R==r)return v[x];ll mid=(L+R)>>1;Downdata(x);if(r<=mid)return Ask(x*2,L,mid,l,r);if(l>mid)return Ask(x*2+1,mid+1,R,l,r);return (Ask(x*2,L,mid,l,mid)+Ask(x*2+1,mid+1,R,mid+1,r))%P; } void Add(ll x){while(x)Change(1,1,n,rfn[top[x]],rfn[x]),x=fa[top[x]];return; } ll Ask(ll x){ll ans=0;while(x)(ans+=Ask(1,1,n,rfn[top[x]],rfn[x]))%=P,x=fa[top[x]];return ans; } signed main() {scanf("%lld%lld%lld",&n,&Q,&k);for(ll i=1;i<=n;i++)pw[i]=power(i,k);for(ll i=2;i<=n;i++){scanf("%lld",&fa[i]);addl(fa[i],i);}for(ll i=1;i<=Q;i++){scanf("%lld%lld",&q[i].l,&q[i].x);q[i].id=i;}sort(q+1,q+1+Q,cmp);top[1]=1;dfs1(1);dfs2(1);Build(1,1,n);ll z=1;for(ll i=1;i<=n;i++){Add(i);while(z<=Q&&q[z].l<=i)ans[q[z].id]=Ask(q[z].x),z++;}for(ll i=1;i<=Q;i++)printf("%lld\n",ans[i]);return 0; }

總結

以上是生活随笔為你收集整理的P5305-[GXOI/GZOI2019]旧词【树链剖分,线段树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。