「GXOI / GZOI2019」旧词

确定这不是思博题

看起来很神仙，本来以为是\([LNOI2014]LCA\)的加强版，结果发现一个点的贡献是\(s_i\times (deep_i^k-(deep_i-1)^k)\)，\(s_i\)就是这个点的子树内部\(1\)到\(x\)点的数量

我们发现我们在树剖的时候利用后面那个东西就能来更新答案和打标机啦

照样离线就好了

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define re register

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

const int maxn=5e4+5;

const int mod=998244353;

inline int read() {

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

struct Ask{int x,y,rk;}q[maxn];

struct E{int v,nxt;}e[maxn];

int deep[maxn],head[maxn],dfn[maxn],id[maxn],top[maxn],fa[maxn],son[maxn];

int sum[maxn],n,m,num,calc[maxn],Ans[maxn],k,__;

int tag[maxn<<2],l[maxn<<2],r[maxn<<2],w[maxn<<2],d[maxn<<2];

inline int cmp(Ask A,Ask B) {return A.x<B.x;}

inline void add(int x,int y) {

	e[++num].v=y;e[num].nxt=head[x];head[x]=num;

}

inline int ksm(int a,int b) {

	int S=1;

	while(b) {if(b&1) S=(1ll*S*a)%mod;b>>=1;a=(1ll*a*a)%mod;}

	return S;

}

void dfs1(int x) {

	sum[x]=1;

	if(!calc[deep[x]])

		calc[deep[x]]=(ksm(deep[x],k)-ksm(deep[x]-1,k)+mod)%mod;

	for(re int i=head[x];i;i=e[i].nxt) {

		if(deep[e[i].v]) continue;

		deep[e[i].v]=deep[x]+1;fa[e[i].v]=x;

		dfs1(e[i].v);sum[x]+=sum[e[i].v];

		if(sum[e[i].v]>sum[son[x]]) son[x]=e[i].v;

	}

}

void dfs2(int x,int topf) {

	top[x]=topf,dfn[x]=++__,id[__]=x;

	if(son[x]) dfs2(son[x],topf);

	for(re int i=head[x];i;i=e[i].nxt)

	if(!top[e[i].v]) dfs2(e[i].v,e[i].v);

}

void build(int x,int y,int i) {

	l[i]=x,r[i]=y;

	if(x==y) {w[i]=calc[deep[id[x]]];return;}

	int mid=x+y>>1;

	build(x,mid,i<<1),build(mid+1,y,i<<1|1);

	w[i]=(w[i<<1]+w[i<<1|1])%mod;

}

inline void pushdown(int i) {

	if(!tag[i]) return;

	tag[i<<1]+=tag[i];tag[i<<1|1]+=tag[i];

	d[i<<1]=(d[i<<1]+1ll*w[i<<1]*tag[i]%mod)%mod;

	d[i<<1|1]=(d[i<<1|1]+1ll*w[i<<1|1]*tag[i]%mod)%mod;

	tag[i]=0;

}

void change(int x,int y,int i) {

	if(x<=l[i]&&y>=r[i]) {

		d[i]=(d[i]+w[i])%mod;

		tag[i]++;

		return;

	}

	pushdown(i);

	int mid=l[i]+r[i]>>1;

	if(x<=mid) change(x,y,i<<1);

	if(y>mid) change(x,y,i<<1|1);

	d[i]=(d[i<<1]+d[i<<1|1])%mod;

}

int query(int x,int y,int i) {

	if(x<=l[i]&&y>=r[i]) return d[i];

	pushdown(i);

	int mid=l[i]+r[i]>>1,tot=0;

	if(x<=mid) tot=(tot+query(x,y,i<<1))%mod;

	if(y>mid) tot=(tot+query(x,y,i<<1|1))%mod;

	return tot;

}

inline void modify(int x) {

	while(top[x])

		change(dfn[top[x]],dfn[x],1),x=fa[top[x]];

}

inline int ask(int x) {

	int tmp=0;

	while(top[x])

		tmp=(tmp+query(dfn[top[x]],dfn[x],1))%mod,x=fa[top[x]];

	return tmp;

}

int main() {

	n=read(),m=read(),k=read();

	for(re int x,i=2;i<=n;i++)

		x=read(),add(x,i);

	calc[1]=deep[1]=1,dfs1(1),dfs2(1,1);build(1,n,1);

	for(re int i=1;i<=m;i++)

		q[i].x=read(),q[i].y=read(),q[i].rk=i;

	std::sort(q+1,q+m+1,cmp);int now=1;

	for(re int i=1;i<=n;i++) {

		modify(i);

		while(now<=m&&q[now].x==i)

			Ans[q[now].rk]=ask(q[now].y),now++;

	}

	for(re int i=1;i<=m;i++) printf("%d\n",Ans[i]);

	return 0;

}

巴特西

「GXOI / GZOI2019」旧词

最新文章

热门文章