题解

这题很明显发现一个点到另一个点，必然最多只有一个进入下界的点和一个出来的点

分类讨论入点和出点的位置

要么都在 \(u->lca\) 或都在 \(lca->v\) 或分别有一个

那就有一个倍增做法

维护最优入点和最优出点即可

但考场并没想到这种方法

反而只想到了没脑的倍增维护矩阵转移的方法

我们设 \(f_{u,0/1}\) 表示从它的儿子 \(v\) 过来的最优答案

把转移式子写成矩阵的形式，倍增维护即可

但我的常数太大了，沦为和暴力老哥同分

\(Code\)

#pragma GCC optimize(3)

#pragma GCC optimize("inline")

#pragma GCC optimize("Ofast")

#pragma GCC target("sse3","sse2","sse")

#pragma GCC diagnostic error "-std=c++14"

#pragma GCC diagnostic error "-fwhole-program"

#pragma GCC diagnostic error "-fcse-skip-blocks"

#pragma GCC diagnostic error "-funsafe-loop-optimizations"

#pragma GCC optimize("fast-math","unroll-loops","no-stack-protector","inline")

#include<cstdio>

#include<iostream>

#define LL long long

using namespace std;

const int N = 2e5 + 5;

int n;

LL a[N];

inline void read(int &x)

{

	x = 0; int f = 1; char ch = getchar();

	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = getchar();

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

	x *= f;

}

inline void read(LL &x)

{

	x = 0; int f = 1; char ch = getchar();

	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = getchar();

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

	x *= f;

}

int h[N], tot;

struct edge{int to, nxt; LL w;}e[N << 1];

inline void add(int x, int y, LL z){e[++tot] = edge{y, h[x], z}, h[x] = tot;}

const LL INF = 1e18;

struct Matrix{

	LL a[3][3];

	inline Matrix()

	{

		for(register int i = 0; i < 3; i++)

			for(register int j = 0; j < 3; j++) a[i][j] = INF;

	}

	inline Matrix operator * (const Matrix &b)

	{

		Matrix c;

		for(register int i = 0; i < 3; i++)

			for(register int j = 0; j < 3; j++)

				for(register int k = 0; k < 3; k++)

				c.a[i][j] = min(c.a[i][j], a[i][k] + b.a[k][j]);

		return c;

	}

}f[N][20];

inline Matrix I()

{

	Matrix c;

	c.a[0][0] = c.a[1][1] = c.a[2][2] = 0;

	return c;

}

inline Matrix BOT(int u)

{

	Matrix c;

	c.a[0][0] = c.a[1][0] = 0, c.a[2][0] = a[u];

	return c;

}

inline Matrix Node(int u, int v, LL w)

{

	Matrix c;

	c.a[0][0] = 8 * w, c.a[0][1] = w + a[u] + a[v], c.a[0][2] = a[u] + w;

	c.a[1][0] = 8 * w, c.a[1][1] = w + a[u] + a[v], c.a[1][2] = a[u] + w;

	c.a[2][0] = 8 * w + a[u], c.a[2][1] = w + a[v], c.a[2][2] = w;

	return c;

}

int dep[N], anc[N][20], d[N];

void bfs()

{

	int head = 0, tail = 1;

	d[1] = 1;

	while (head < tail)

	{

		int x = d[++head];

		for(register int i = 1; i <= 18; i++)

		if (anc[x][i - 1]) anc[x][i] = anc[anc[x][i - 1]][i - 1], f[x][i] =  f[anc[x][i - 1]][i - 1] * f[x][i - 1];

		else break;

		for(register int i = h[x]; i; i = e[i].nxt)

		{

			int v = e[i].to;

			if (v == anc[x][0]) continue;

			anc[v][0] = x, f[v][0] = Node(x, v, e[i].w);

			dep[v] = dep[x] + 1, d[++tail] = v;

		}

	}

}

inline LL getans(int x, int y)

{

	if (dep[x] < dep[y]) swap(x, y);

	int deep = dep[x] - dep[y];

	Matrix retx = I(), rety = I(), Bx = BOT(x), By = BOT(y);

	for(register int i = 18; i >= 0; i--)

	if ((deep >> i) & 1) retx = f[x][i] * retx , x = anc[x][i];

	if (x == y)

	{

		retx = retx * Bx;

		return min(retx.a[0][0], retx.a[2][0] + a[x]);

	}

	for(register int i = 18; i >= 0; i--)

	if (anc[x][i] ^ anc[y][i])

	{

		retx = f[x][i] * retx , rety = f[y][i] * rety;

		x = anc[x][i], y = anc[y][i];

	}

	retx = f[x][0] * retx * Bx, rety = f[y][0] * rety * By;

	return min(min(retx.a[0][0] + rety.a[0][0], retx.a[2][0] + rety.a[2][0]),

		min(retx.a[0][0] + rety.a[2][0] + a[anc[x][0]], retx.a[2][0] + rety.a[0][0] + a[anc[x][0]]));

}

int main()

{

	freopen("minecraft.in", "r", stdin);

	freopen("minecraft.out", "w", stdout);

	read(n);

	for(register int i = 1; i <= n; i++) read(a[i]);

	int x, y; LL z;

	for(register int i = 1; i < n; i++) read(x), read(y), read(z), add(x, y, z), add(y, x, z);

	bfs();

	int q; read(q);

	for(; q; --q) read(x), read(y), printf("%lld\n", getans(x, y));

}

巴特西

JZOJ 2474. 【GDKOI 2021普及组DAY2】我的世界

题解

\(Code\)

最新文章

热门文章