abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ J2474 【我的世界】

发表于

Description

用两棵有 $n$ 个点的有边权的树，分别描绘主世界和异世界。现在有 $q$ 次独立的行动计划，每次从主世界的点 $u_i$ 走简单路径到主世界的点 $v_i$。现在你可以用 $a_p$ 的时间在两个世界的点 $p$ 之间的穿梭一次。若在异世界走一条边需要 $w$ 的时间，则在主世界走这条边则需要 $8w$ 的时间。问你完成每次行动计划所需的最小时间。

Solution

很有意思的一道题啊。

考虑设 $f_{i, j, 0 / 1, 0 / 1}$ 表示当前在点 $i$，往上跳 $2^j$ 步，在这一段的起点处在主世界 / 异世界，结尾处在主世界 / 异世界的情况下所需的最小代价。

然后对这几种情况进行转移即可。写这题的转移真的很舒爽，因为长度很统一。

当然本题也有正常一点的倍增做法，在此就不赘述了。

由于我被卡常了，所以……

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <cstdio>
#include <cstdlib>
#define maxN 200010
struct Edge{ long long x, y, c, g; } b[maxN << 1];
long long len = 0;
long long val[maxN], h[maxN];
long long queue[maxN], dep[maxN];
long long f[maxN][20], dp[maxN][20][2][2];
long long read ()
{
	long long x = 0;
	char c = getchar();
	while(c < '0' || c > '9')
	{
		c = getchar();
	}
	while(c >= '0' && c <= '9')
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}
	return x;
}
long long min (long long x, long long y)
{
	return x < y ? x : y;
}
void swap (long long &x, long long &y)
{
	long long t = x;
	x = y;
	y = t;
}
void ins (long long x, long long y, long long c)
{
	len++;
	b[len].x = x;
	b[len].y = y;
	b[len].c = c;
	b[len].g = h[x];
	h[x] = len;
}
void bfs ()
{
	long long head = 1, tail = 2;
	dep[1] = 1, queue[head] = 1;
	while(head < tail)
	{
		long long x = queue[head++];
		for(long long i = h[x];i;i = b[i].g)
		{
			long long y = b[i].y, c = b[i].c;
			if(!dep[y])
			{
				f[y][0] = x;
				dep[y] = dep[x] + 1;
				dp[y][0][0][0] = min((c << 3), val[x] + c + val[y]);
				dp[y][0][0][1] = min((c << 3) + val[x], c + val[y]);
				dp[y][0][1][0] = min(val[y] + (c << 3), c + val[x]);
				dp[y][0][1][1] = min(c, val[x] + (c << 3) + val[y]);
				queue[tail++] = y;
			}
		}
	}
}
long long work (long long x, long long y)
{
	if(dep[x] < dep[y])
	{
		swap(x, y);
	}
	long long resA = 0, resB = val[x], resC = 0, resD = val[y];
	for(long long i = 19;i >= 0; i--)
	{
		if(dep[f[x][i]] >= dep[y])
		{
			long long resAA = min(resA + dp[x][i][0][0], resB + dp[x][i][1][0]);
			long long resBB = min(resA + dp[x][i][0][1], resB + dp[x][i][1][1]);
			resA = resAA, resB = resBB;
			x = f[x][i];
		}
	}
	if(x == y)
	{
		return min(resA, resB + val[x]);
	}
	for(long long i = 19;i >= 0; i--)
	{
		if(f[x][i] != f[y][i])
		{
			long long resAA = min(resA + dp[x][i][0][0], resB + dp[x][i][1][0]);
			long long resBB = min(resA + dp[x][i][0][1], resB + dp[x][i][1][1]);
			long long resCC = min(resC + dp[y][i][0][0], resD + dp[y][i][1][0]);
			long long resDD = min(resC + dp[y][i][0][1], resD + dp[y][i][1][1]);
			resA = resAA, resB = resBB, resC = resCC, resD = resDD;
			x = f[x][i], y = f[y][i];
		}
	}
	long long resAA = min(resA + dp[x][0][0][0], resB + dp[x][0][1][0]);
	long long resBB = min(resA + dp[x][0][0][1], resB + dp[x][0][1][1]);
	long long resCC = min(resC + dp[y][0][0][0], resD + dp[y][0][1][0]);
	long long resDD = min(resC + dp[y][0][0][1], resD + dp[y][0][1][1]);
	resA = resAA, resB = resBB, resC = resCC, resD = resDD;
	return min(resA + resC, min(resB + resD, min(resA + resD + val[f[x][0]], resB + resC + val[f[x][0]])));
}
int main ()
{
	long long n = read(), Q = 0;
	for(long long i = 1;i <= n; i++)
	{
		val[i] = read();
	}
	for(long long i = 1;i < n; i++)
	{
		long long x = read(), y = read(), c = read();
		ins(x, y, c), ins(y, x, c);
	}
	bfs();
	for(long long j = 1;j <= 19; j++)
	{
		for(long long i = 1;i <= n; i++)
		{
			long long x = f[i][j - 1];
			f[i][j] = f[x][j - 1];
			dp[i][j][0][0] = min(dp[i][j - 1][0][1] + dp[x][j - 1][1][0], dp[i][j - 1][0][0] + dp[x][j - 1][0][0]);
			dp[i][j][0][1] = min(dp[i][j - 1][0][0] + dp[x][j - 1][0][1], dp[i][j - 1][0][1] + dp[x][j - 1][1][1]);
			dp[i][j][1][0] = min(dp[i][j - 1][1][0] + dp[x][j - 1][0][0], dp[i][j - 1][1][1] + dp[x][j - 1][1][0]);
			dp[i][j][1][1] = min(dp[i][j - 1][1][0] + dp[x][j - 1][0][1], dp[i][j - 1][1][1] + dp[x][j - 1][1][1]);
		}
	}
	Q = read();
	while(Q--)
	{
		long long x = read(), y = read();
		printf("%lld\n", work(x, y));
	}
	return 0;
}