目录
显示
题目链接
https://www.luogu.com.cn/problem/P5305
题解
本题显然是 [LNOI2014]LCA 的推广。
我们还是采用和那道题一样的方法来维护 LCA 深度和。唯一的区别就在于对 k 次方这个操作的处理上。
先思考一下 k=1 的情况,我们将路径上所有节点的值加一,究竟是为什么呢?
其实这个操作可以视为一个树上差分的操作。我们执行的修改操作,其实是给点权加上相邻两点深度的差值(k=1 时显然就是 1),而把差分数组累加起来,则就是要求的和。
理解了这一点,我们也不难把这个操作推广到 k \neq 1 的情况了。根据上文所述,对于一个深度为 dep_i 的点,我们执行一次修改操作给它的点权加上的值为 dep_i^k-(dep_i-1)^k。
这样我们就完美地解决了本题。
#include <iostream>
#include <vector>
#include <algorithm>
#define MOD 998244353
using namespace std;
struct query
{
int r,z,id;
bool operator<(const query&a)const
{
return r<a.r;
}
};
struct seg
{
long long sum,tag,ds;
}s[200005];
struct edge
{
int v,next;
}e[50005];
vector<query> q;
int n,Q,k;
int head[50005],ans[50005];
int siz[50005],dep[50005],son[50005],fa[50005],num[50005];
int id[50005],top[50005],cnt;
int dk[50005];
long long fpow(long long x,long long y)
{
long long ans=1;
while(y)
{
if(y&1)ans=ans*x%MOD;
x=x*x%MOD;
y>>=1;
}
return ans;
}
void addedge(int u,int v)
{
e[++cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs1(int u,int f)
{
siz[u]=1;
dep[u]=dep[f]+1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int t)
{
id[u]=++cnt;
num[cnt]=u;
top[u]=t;
if(!son[u])return;
dfs2(son[u],t);
for(int i=head[u];i;i=e[i].next)
if(e[i].v!=son[u])dfs2(e[i].v,e[i].v);
}
void pushup(int root)
{
s[root].sum=(s[root<<1].sum+s[root<<1|1].sum)%MOD;
s[root].ds=(s[root<<1].ds+s[root<<1|1].ds)%MOD;
}
void build(int root,int l,int r)
{
if(l==r)
{
s[root].ds=dk[num[l]];
return;
}
int mid=(l+r)>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
pushup(root);
}
void pushdown(int root)
{
s[root<<1].tag+=s[root].tag;s[root<<1].tag%=MOD;
s[root<<1|1].tag+=s[root].tag;s[root<<1|1].tag%=MOD;
s[root<<1].sum+=s[root].tag*s[root<<1].ds%MOD;s[root<<1].sum%=MOD;
s[root<<1|1].sum+=s[root].tag*s[root<<1|1].ds%MOD;s[root<<1|1].sum%=MOD;
s[root].tag=0;
}
void update(int root,int cl,int cr,int l,int r)
{
if(r<cl||cr<l)return;
if(l<=cl&&cr<=r)
{
s[root].tag++;
s[root].sum=(s[root].sum+s[root].ds)%MOD;
return;
}
pushdown(root);
int mid=(cl+cr)>>1;
update(root<<1,cl,mid,l,r);
update(root<<1|1,mid+1,cr,l,r);
pushup(root);
}
int query(int root,int cl,int cr,int l,int r)
{
if(r<cl||cr<l)return 0;
if(l<=cl&&cr<=r)return s[root].sum;
pushdown(root);
int mid=(cl+cr)>>1;
return (query(root<<1,cl,mid,l,r)+query(root<<1|1,mid+1,cr,l,r))%MOD;
}
void update_chain(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
update(1,1,n,id[x],id[y]);
}
int query_chain(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=(ans+query(1,1,n,id[top[x]],id[x]))%MOD;
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ans=(ans+query(1,1,n,id[x],id[y]))%MOD;
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>Q>>k;
for(int i=2;i<=n;i++)
{
cin>>fa[i];
addedge(fa[i],i);
}
cnt=0;
dfs1(1,1);
dfs2(1,1);
for(int i=1;i<=n;i++)
dk[i]=(fpow(dep[i],k)-fpow(dep[i]-1,k)+MOD)%MOD;
build(1,1,n);
for(int i=1;i<=Q;i++)
{
int r,z;
cin>>r>>z;
q.push_back({r,z,i});
}
sort(q.begin(),q.end());
int u=1;
for(auto i:q)
{
while(u<=i.r)
{
update_chain(1,u);
u++;
}
ans[i.id]=query_chain(1,i.z);
}
for(int i=1;i<=Q;i++)
cout<<(ans[i]+MOD)%MOD<<endl;
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
#define MOD 998244353
using namespace std;
struct query
{
int r,z,id;
bool operator<(const query&a)const
{
return r<a.r;
}
};
struct seg
{
long long sum,tag,ds;
}s[200005];
struct edge
{
int v,next;
}e[50005];
vector<query> q;
int n,Q,k;
int head[50005],ans[50005];
int siz[50005],dep[50005],son[50005],fa[50005],num[50005];
int id[50005],top[50005],cnt;
int dk[50005];
long long fpow(long long x,long long y)
{
long long ans=1;
while(y)
{
if(y&1)ans=ans*x%MOD;
x=x*x%MOD;
y>>=1;
}
return ans;
}
void addedge(int u,int v)
{
e[++cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs1(int u,int f)
{
siz[u]=1;
dep[u]=dep[f]+1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int t)
{
id[u]=++cnt;
num[cnt]=u;
top[u]=t;
if(!son[u])return;
dfs2(son[u],t);
for(int i=head[u];i;i=e[i].next)
if(e[i].v!=son[u])dfs2(e[i].v,e[i].v);
}
void pushup(int root)
{
s[root].sum=(s[root<<1].sum+s[root<<1|1].sum)%MOD;
s[root].ds=(s[root<<1].ds+s[root<<1|1].ds)%MOD;
}
void build(int root,int l,int r)
{
if(l==r)
{
s[root].ds=dk[num[l]];
return;
}
int mid=(l+r)>>1;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
pushup(root);
}
void pushdown(int root)
{
s[root<<1].tag+=s[root].tag;s[root<<1].tag%=MOD;
s[root<<1|1].tag+=s[root].tag;s[root<<1|1].tag%=MOD;
s[root<<1].sum+=s[root].tag*s[root<<1].ds%MOD;s[root<<1].sum%=MOD;
s[root<<1|1].sum+=s[root].tag*s[root<<1|1].ds%MOD;s[root<<1|1].sum%=MOD;
s[root].tag=0;
}
void update(int root,int cl,int cr,int l,int r)
{
if(r<cl||cr<l)return;
if(l<=cl&&cr<=r)
{
s[root].tag++;
s[root].sum=(s[root].sum+s[root].ds)%MOD;
return;
}
pushdown(root);
int mid=(cl+cr)>>1;
update(root<<1,cl,mid,l,r);
update(root<<1|1,mid+1,cr,l,r);
pushup(root);
}
int query(int root,int cl,int cr,int l,int r)
{
if(r<cl||cr<l)return 0;
if(l<=cl&&cr<=r)return s[root].sum;
pushdown(root);
int mid=(cl+cr)>>1;
return (query(root<<1,cl,mid,l,r)+query(root<<1|1,mid+1,cr,l,r))%MOD;
}
void update_chain(int x,int y)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
update(1,1,n,id[x],id[y]);
}
int query_chain(int x,int y)
{
int ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=(ans+query(1,1,n,id[top[x]],id[x]))%MOD;
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ans=(ans+query(1,1,n,id[x],id[y]))%MOD;
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>Q>>k;
for(int i=2;i<=n;i++)
{
cin>>fa[i];
addedge(fa[i],i);
}
cnt=0;
dfs1(1,1);
dfs2(1,1);
for(int i=1;i<=n;i++)
dk[i]=(fpow(dep[i],k)-fpow(dep[i]-1,k)+MOD)%MOD;
build(1,1,n);
for(int i=1;i<=Q;i++)
{
int r,z;
cin>>r>>z;
q.push_back({r,z,i});
}
sort(q.begin(),q.end());
int u=1;
for(auto i:q)
{
while(u<=i.r)
{
update_chain(1,u);
u++;
}
ans[i.id]=query_chain(1,i.z);
}
for(int i=1;i<=Q;i++)
cout<<(ans[i]+MOD)%MOD<<endl;
return 0;
}
#include <iostream> #include <vector> #include <algorithm> #define MOD 998244353 using namespace std; struct query { int r,z,id; bool operator<(const query&a)const { return r<a.r; } }; struct seg { long long sum,tag,ds; }s[200005]; struct edge { int v,next; }e[50005]; vector<query> q; int n,Q,k; int head[50005],ans[50005]; int siz[50005],dep[50005],son[50005],fa[50005],num[50005]; int id[50005],top[50005],cnt; int dk[50005]; long long fpow(long long x,long long y) { long long ans=1; while(y) { if(y&1)ans=ans*x%MOD; x=x*x%MOD; y>>=1; } return ans; } void addedge(int u,int v) { e[++cnt].v=v; e[cnt].next=head[u]; head[u]=cnt; } void dfs1(int u,int f) { siz[u]=1; dep[u]=dep[f]+1; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; dfs1(v,u); siz[u]+=siz[v]; if(siz[v]>siz[son[u]])son[u]=v; } } void dfs2(int u,int t) { id[u]=++cnt; num[cnt]=u; top[u]=t; if(!son[u])return; dfs2(son[u],t); for(int i=head[u];i;i=e[i].next) if(e[i].v!=son[u])dfs2(e[i].v,e[i].v); } void pushup(int root) { s[root].sum=(s[root<<1].sum+s[root<<1|1].sum)%MOD; s[root].ds=(s[root<<1].ds+s[root<<1|1].ds)%MOD; } void build(int root,int l,int r) { if(l==r) { s[root].ds=dk[num[l]]; return; } int mid=(l+r)>>1; build(root<<1,l,mid); build(root<<1|1,mid+1,r); pushup(root); } void pushdown(int root) { s[root<<1].tag+=s[root].tag;s[root<<1].tag%=MOD; s[root<<1|1].tag+=s[root].tag;s[root<<1|1].tag%=MOD; s[root<<1].sum+=s[root].tag*s[root<<1].ds%MOD;s[root<<1].sum%=MOD; s[root<<1|1].sum+=s[root].tag*s[root<<1|1].ds%MOD;s[root<<1|1].sum%=MOD; s[root].tag=0; } void update(int root,int cl,int cr,int l,int r) { if(r<cl||cr<l)return; if(l<=cl&&cr<=r) { s[root].tag++; s[root].sum=(s[root].sum+s[root].ds)%MOD; return; } pushdown(root); int mid=(cl+cr)>>1; update(root<<1,cl,mid,l,r); update(root<<1|1,mid+1,cr,l,r); pushup(root); } int query(int root,int cl,int cr,int l,int r) { if(r<cl||cr<l)return 0; if(l<=cl&&cr<=r)return s[root].sum; pushdown(root); int mid=(cl+cr)>>1; return (query(root<<1,cl,mid,l,r)+query(root<<1|1,mid+1,cr,l,r))%MOD; } void update_chain(int x,int y) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); update(1,1,n,id[top[x]],id[x]); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); update(1,1,n,id[x],id[y]); } int query_chain(int x,int y) { int ans=0; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); ans=(ans+query(1,1,n,id[top[x]],id[x]))%MOD; x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); ans=(ans+query(1,1,n,id[x],id[y]))%MOD; return ans; } int main() { ios::sync_with_stdio(false); cin>>n>>Q>>k; for(int i=2;i<=n;i++) { cin>>fa[i]; addedge(fa[i],i); } cnt=0; dfs1(1,1); dfs2(1,1); for(int i=1;i<=n;i++) dk[i]=(fpow(dep[i],k)-fpow(dep[i]-1,k)+MOD)%MOD; build(1,1,n); for(int i=1;i<=Q;i++) { int r,z; cin>>r>>z; q.push_back({r,z,i}); } sort(q.begin(),q.end()); int u=1; for(auto i:q) { while(u<=i.r) { update_chain(1,u); u++; } ans[i.id]=query_chain(1,i.z); } for(int i=1;i<=Q;i++) cout<<(ans[i]+MOD)%MOD<<endl; return 0; }