Luogu P3591 [POI2015]ODW 题解

Description

题目链接

给定一棵n个点的树,树上每条边的长度都为1,第i个点的权值为a[i]。Byteasar想要走遍这整棵树,他会按照某个1到n的全排列b走n-1次,第i次他会从b[i]点走到b[i+1]点,并且这一次的步伐大小为c[i]。对于一次行走,假设起点为x,终点为y,步伐为k,那么Byteasar会从x开始,每步往前走k步,如果最后不足k步就能到达y,那么他会一步走到y。请帮助Byteasar统计出每一次行走时经过的所有点的权值和。

Solution

设一个阈值$S=\sqrt N$。

若$c\leq S$,则预处理出答案,前缀和一下即可。

若$c>S$,则直接暴力跳。

Code

#include<cstdio>
#define S 225
int n,a[50010],b[50010],c[50010],fir[50010],nxt[50010<<1],son[50010<<1],tot,sum[50010],dep[50010],f[50010][20],s[50010][233];
inline void add(int x,int y){++tot,nxt[tot]=fir[x],fir[x]=tot,son[tot]=y;}
inline void dfs0(int x){
	sum[x]+=a[x];
	for(int i=0;i<16;i++) f[x][i+1]=f[f[x][i]][i];
	for(int to,i=fir[x];i;i=nxt[i]){
		to=son[i];
		if(dep[to]) continue ;
		dep[to]=dep[x]+1;
		f[to][0]=x;
		sum[to]=sum[x];
		dfs0(to);
	}
}
inline int getlca(int x,int y){
	if(dep[x]<dep[y]) x^=y^=x^=y;
	for(int i=16;~i;i--)
		if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	for(int i=16;~i;i--)
		if(f[x][i]^f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
inline int getfa(int x,int d){
	for(int i=16;~i;i--)
		if(d>>i&1) x=f[x][i];
	return x;
}
inline void dfs(int x){
	int fa=f[x][0];
	for(int i=2;i<=S;i++) fa=f[fa][0],s[x][i]=s[fa][i]+a[x];
	for(int to,i=fir[x];i;i=nxt[i]){
		to=son[i];
		if(dep[x]<dep[to]) dfs(to);
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int x,y,i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
	for(int i=1;i<=n;i++) scanf("%d",&b[i]);
	for(int i=1;i<n;i++) scanf("%d",&c[i]);
	dep[1]=1;dfs0(1);
	dfs(1);
	for(int x,y,k,lca,i=1;i<n;i++){
		x=b[i],y=b[i+1],k=c[i],lca=getlca(x,y);
		if(k==1) printf("%d\n",sum[x]+sum[y]-sum[lca]-sum[f[lca][0]]);
		else if(k<=S){
			int Ans=s[x][k],d=(dep[x]-dep[lca])%k==0?k:(dep[x]-dep[lca])%k;
			for(int i=16;~i;i--)
				if(dep[f[x][i]]-dep[lca]>=d) x=f[x][i];
			Ans+=a[x]-s[x][k];
			if(dep[x]+dep[y]-(dep[lca]<<1)>=k){
				d=k-dep[x]+dep[lca];
				x=y;
				for(int i=16;~i;i--)
					if(dep[f[x][i]]-dep[lca]>=d) x=f[x][i];
				d=(dep[y]-dep[x])%k;
				if(d) Ans+=a[y];
				y=getfa(y,d);
				Ans+=s[y][k]-s[x][k]+a[x];
			}else Ans+=a[y];
			printf("%d\n",Ans);
		}else{
			int Ans=0;
			while(dep[x]-dep[lca]>k) Ans+=a[x],x=getfa(x,k);
			Ans+=a[x];
			if(dep[x]+dep[y]-(dep[lca]<<1)>=k){
				int d=k-dep[x]+dep[lca];
				x=y;
				for(int i=16;~i;i--)
					if(dep[f[x][i]]-dep[lca]>=d) x=f[x][i];
				d=(dep[y]-dep[x])%k;
				if(d) Ans+=a[y];
				y=getfa(y,d);
				while(dep[y]-dep[x]>=k) Ans+=a[y],y=getfa(y,k);
				Ans+=a[y];
			}else Ans+=a[y];
			printf("%d\n",Ans);
		}
	}
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇