P9399 「DBOI」Round 1 人生如树

题意

一棵树，两个操作，每个点有点权。

• 给定 \(v, w\)。新建一个点 \(u'\) 点权为 \(w\)，连接 \(u' \to v\)。

• 询问 \(u_1 \to v_1\) 的点权的序列 \(a\)，使 \(a_i \to a_i + i\)，与 \(u_2 \to v_2\) 的点权的序列 \(b\) 的最长公共前缀。

Sol

其实这道题并没有什么好说的，看懂题基本就得出做法了。

主要是细节有点多。

注意到这个 \(a_i + i\) 的形式很能哈希，发现哈希就直接能做。

由于要二分 LCP，会多挂只 \(log\)，树剖上线段树二分是不好做的。

考虑先把 LCA 求出来，然后考虑倍增分别维护这两条链的哈希。

做完了。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <tuple>
#include <cmath>
#include <tuple>
#include <vector>
#define int long long
#define tupl tuple <int, int, int, int>
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
const int N = 2e5 + 5, M = 4e5 + 5, inf = 2e18;

namespace G {

array <int, N> fir;
array <int, M> nex, to;

int cnt = 1;

void add(int x, int y) {
	cnt++;
	nex[cnt] = fir[x];
	to[cnt] = y;
	fir[x] = cnt;
}

}

namespace Esl {

array <int, N> fa, dep;
array <int, M> idx, dfn;
int cnt;

void dfs(int x) {
	cnt++;
	dfn[x] = cnt;
	idx[cnt] = x;
	for (int i = G::fir[x]; i; i = G::nex[i]) {
		if (G::to[i] == fa[x]) continue;
		fa[G::to[i]] = x;
		dep[G::to[i]] = dep[x] + 1;
		dfs(G::to[i]), cnt++, idx[cnt] = x;
	}
}

array <array <int, 22>, M> sT;
array <int, M> lg;

void init() {
	for (int i = 1; i <= cnt; i++)
		lg[i] = log2(i), sT[i].fill(inf);
	for (int i = 1; i <= cnt; i++)
		sT[i][0] = dfn[idx[i]];
	for (int j = 1; j <= 21; j++)
		for (int i = 1; i + (1 << j) - 1 <= cnt; i++)
			sT[i][j] = min(sT[i][j - 1], sT[i + (1 << (j - 1))][j - 1]);
}

int query(int l, int r) {
	tie(l, r) = minmax(dfn[l], dfn[r]);
	int len = lg[r - l + 1];
	return idx[min(sT[l][len], sT[r - (1 << len) + 1][len])];
}

}

array <array <int, 22>, N> f1, f2;
array <array <int, 22>, N> fa;
array <int, N> idx;

void dfs(int x) {
	fa[x][0] = Esl::fa[x];
	for (int i = 1; i <= 21; i++) {
		fa[x][i] = fa[fa[x][i - 1]][i - 1];
		f1[x][i] = idx[1 << (i - 1)] * f1[x][i - 1] + f1[fa[x][i - 1]][i - 1];
		f2[x][i] = idx[1 << (i - 1)] * f2[fa[x][i - 1]][i - 1] + f2[x][i - 1];
	}
	for (int i = G::fir[x]; i; i = G::nex[i]) {
		if (G::to[i] == Esl::fa[x]) continue;
		dfs(G::to[i]);
	}
}

int getfa(int x, int k) {
	for (int i = 21; ~i; i--)
		if (k & (1 << i))
			x = fa[x][i];
	return x;
}

int gethash(int u, int v, int k) {
	using Esl::dep;
	int lcA = Esl::query(u, v);
	int tp1 = min(dep[u] - dep[lcA] + 1, k), tp2 = k - tp1;
	int _u = u, hs1 = 0;
	for (int i = 21; ~i; i--)
		if (tp1 & (1 << i))
			hs1 = f1[_u][i] + hs1 * idx[1 << i], _u = fa[_u][i];
	int _v = getfa(v, dep[v] - dep[lcA] - tp2), hs2 = 0, now = 0;
	for (int i = 21; ~i; i--)
		if (tp2 & (1 << i))
			hs2 = hs2 + f2[_v][i] * idx[now], _v = fa[_v][i], now |= (1 << i);
	return hs1 * idx[k - tp1] + hs2;
}

vector <tupl> qrl;
array <int, N> s, tp0;

signed main() {
	int n = read(), m = read(), id = read();
	for (int i = 1; i <= n; i++)
		s[i] = read();
	for (int i = 2, x, y; i <= n; i++)
		x = read(), y = read(), G::add(x, y), G::add(y, x);
	for (int i = 1; i <= m; i++) {
		int op = read();
		if (op == 1) {
			tupl tp0;
			get <0>(tp0) = read(), get <1>(tp0) = read();
			get <2>(tp0) = read(), get <3>(tp0) = read();
			qrl.push_back(tp0);
		}
		else {
			int x = read(), y = read();
			n++;
			G::add(n, x), G::add(x, n), s[n] = y;
		}
	}
	Esl::dfs(1), Esl::init();
	for (int i = 1; i <= n; i++)
		f1[i][0] = f2[i][0] = s[i];
	idx[0] = 1;
	for (int i = 1; i <= 2e5; i++)
		idx[i] = idx[i - 1] * 131ll;
	for (int i = 1; i <= 2e5; i++)
		tp0[i] = tp0[i - 1] * 131ll + i;
	dfs(1);
	/* write(gethash(1, 6, 4)), puts("@"); */
	/* exit(0); */
	/* write(gethash(8, 10, 2)), puts("@"); */
	for (auto [u1, v1, u2, v2] : qrl) {
		int lcA1 = Esl::query(u1, v1), lcA2 = Esl::query(u2, v2);
		using Esl::dep;
		int r = min(dep[u1] + dep[v1] - 2 * dep[lcA1],
					dep[u2] + dep[v2] - 2 * dep[lcA2]) + 1;
		int l = 1, ans = 0;
		while (l <= r) {
			int mid = (l + r) >> 1;
			/* write(l), putchar(32); */
			/* write(r), putchar(32); */
			/* write(mid), puts(""); */
			if (gethash(u1, v1, mid) + tp0[mid] ==
				gethash(u2, v2, mid))
				l = mid + 1, ans = mid;
			else
				r = mid - 1;
		}
		write(ans), puts("");
	}
	return 0;
}