BZOJ 4381 Odwiedziny

发表于 | 更新于

Link

很喵的想法，，虽然应该比较常见

Solution

当步长比较大的时候，步数就会很小 所以步长>n>\sqrt n的时候暴力走 只计算步长≤n\le \sqrt n的情况，就大大简化了问题！！！ 这样对于小步长的计算，只需要预处理数组sum[pos][B]sum[pos][B]，表示步长为BB的时候走到根节点的权值和。 配合倍增和一点很多细节判断就可以过掉了。

Tips

没错，这种思路要记住：大范围暴力，小范围预处理！(怎么感觉不太对的样子233)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include "lucida"

using std::swap;
const int MAXN=5e4+11,B=250,LOG=16,MAXLOG=20,MAXB=B+1;
struct Edge {
	int to;
	Edge *pre;
	Edge(int to,Edge *pre):to(to),pre(pre){}
	void *operator new(size_t);
}*id[MAXN];
void *Edge::operator new(size_t) {
	static Edge *Pool=(Edge*)malloc((MAXN<<1)*sizeof(Edge)),*Me=Pool;
	return Me++;//Me...!!
}
void Adde(int f,int t) {
	id[f]=new Edge(t,id[f]);
	id[t]=new Edge(f,id[t]);
}
int dfs[MAXN<<1],par[MAXN][MAXLOG],dep[MAXN]={0,1},dc,lbd[MAXN],rbd[MAXN],w[MAXN],sum[MAXN][MAXB],stack[MAXN],top;
void DFS(int pos) {
	for(int lg=1;lg<=LOG;++lg)
		par[pos][lg]=par[par[pos][lg-1]][lg-1];
	stack[++top]=pos;
	dfs[++dc]=pos;lbd[pos]=dc;
	for(int b=1;b<=B;++b) {
		sum[pos][b]=w[pos]+(top>b?sum[stack[top-b]][b]:0);
	}
	for(Edge *e=id[pos];e;e=e->pre) {
		int u=e->to;
		if(u==par[pos][0]) continue;
		par[u][0]=pos;
		dep[u]=dep[pos]+1;
		DFS(u);
		dfs[++dc]=pos;
	}
	rbd[pos]=dc;top--;
}
int f[MAXN<<1][MAXLOG],log_2[MAXN<<1];
void SparseTable() {
	log_2[0]=-1;
	for(int i=1;i<=dc;++i) {
		f[i][0]=dfs[i];
		log_2[i]=log_2[i>>1]+1;
	}
	for(int j=1,endj=log_2[dc];j<=endj;++j)
		for(int i=1,endi=dc-(1<<j)+1;i<=endi;++i) {
			int pl=f[i][j-1],pr=f[i+(1<<j>>1)][j-1];
			f[i][j]=dep[pl]<dep[pr]?pl:pr;
		}
}
int LCA(int p1,int p2) {
	p1=lbd[p1],p2=lbd[p2];
	if(p1>p2) swap(p1,p2);
	int lg=log_2[p2-p1+1],pl,pr;
	return dep[pl=f[p1][lg]]<dep[pr=f[p2-(1<<lg)+1][lg]]?pl:pr;
}
int Jump(int pos,int c) {
	for(int lg=log_2[c];~lg;--lg)
		if((1<<lg)<=c) {
			c-=(1<<lg);
			pos=par[pos][lg];
		}
	return pos;
}
int Sum(int s,int t,int c) {
	if(c<B)
		return sum[s][c]-sum[t][c]+w[t];
	int res=w[s];
	while(s!=t) {
		s=Jump(s,c);
		res+=w[s];
	}
	return res;
}
int Walk(int s,int t,int c) {
	//sum[pos][B] 当前位置开始c步间隔跳到根节点的sumval
	int lca=LCA(s,t),rs=0,rt=0;
	//Part 1 让指针s走到最后一个<=lca的节点上
	//Part 2 让指针t走到第一个>lca的节点上
	int len=dep[s]-dep[lca];
	if(len<c)
		rs=w[s];
	else {
		len-=len%c;int dest=Jump(s,len);
		rs=Sum(s,dest,c);
		s=dest;
	}
	if(s!=t) {
		len=dep[t]-dep[lca];
		int dis2next=c-(dep[s]-dep[lca]),
			remain=len-dis2next;
		rt=w[t];
		if(remain>0) {
			len=remain;
			remain=len%c;
			t=Jump(t,remain);
			rt+=(bool)remain*w[t];
			if(len>remain) {
				len-=remain;
				int dest=Jump(t,len);
				rt+=Sum(t,dest,c)-w[t];
			} 
		}
	}
	return rs+rt;
}
int main() {

//	freopen("input","r",stdin);
	int n;is>>n;
	for(int i=1;i<=n;++i)
		is>>w[i];
	for(int i=1;i<=n-1;++i) {
		int u,v;
		is>>u>>v;
		Adde(u,v);
	}
	DFS(1);
	SparseTable();
	static int route[MAXN],step[MAXN];
	for(int i=1;i<=n;++i)
		is>>route[i];
	for(int i=1;i<=n-1;++i) {
		is>>step[i];
		os<<Walk(route[i],route[i+1],step[i])<<'\n';
	}
	return 0;
}