P11755 [COCI 2024/2025 #5] 树树 2 / Stablo II 题解

il int read() {
	int re = 0;
	char in = getchar();

	while (in < '0' || in > '9')
		in = getchar();

	while (in >= '0' && in <= '9') {
		re = re * 10 + in - 48;
		in = getchar();
	}

	return re;
}

il void print(int x) {
	if (x < 10)
		putchar(x + '0');
	else {
		print(x / 10);
		putchar(x % 10 + '0');
	}
}

const int N = 1e6 + 10;
int n, q, head[N], totedge, fa[N], top[N], dep[N], dfn[N], curdfn, siz[N], hs[N], sgtr[N * 4], lazy[N * 4];

struct edge {
	int x, y;
} nxt[N * 2];

void addedge(int x, int y) {
	totedge++;
	nxt[totedge].x = y;
	nxt[totedge].y = head[x];
	head[x] = totedge;
}

void dfs1(int p) {
	siz[p] = 1;

	for (int i = head[p]; i; i = nxt[i].y) {
		if (nxt[i].x != fa[p]) {
			fa[nxt[i].x] = p;
			dep[nxt[i].x] = dep[p] + 1;
			dfs1(nxt[i].x);
			siz[p] += siz[nxt[i].x];

			if (siz[nxt[i].x] > siz[hs[p]])
				hs[p] = nxt[i].x;
		}
	}
}

void dfs2(int p, int curtop) {
	top[p] = curtop;
	curdfn++;
	dfn[p] = curdfn;

	if (!hs[p])
		return;

	dfs2(hs[p], curtop);

	for (int i = head[p]; i; i = nxt[i].y) {
		if (nxt[i].x != fa[p] && nxt[i].x != hs[p])
			dfs2(nxt[i].x, nxt[i].x);
	}
}

void pushdown(int p) {
	sgtr[p * 2] = lazy[p];
	sgtr[p * 2 + 1] = lazy[p];
	lazy[p * 2] = lazy[p];
	lazy[p * 2 + 1] = lazy[p];
	lazy[p] = 0;
}

void upd(int p, int l, int r, int ql, int qr, int val) {
	if (ql <= l and r <= qr) {
		sgtr[p] = val;
		lazy[p] = val;
		return;
	}

	if (lazy[p])
		pushdown(p);

	int mid = (l + r) / 2;

	if (ql <= mid)
		upd(p * 2, l, mid, ql, qr, val);
	if (mid < qr)
		upd(p * 2 + 1, mid + 1, r, ql, qr, val);
}

int ans[N];

void query(int p, int l, int r) {
	if (l == r) {
		ans[l] = sgtr[p];
		return;
	}

	if (lazy[p])
		pushdown(p);

	int mid = (l + r) / 2;
	query(p * 2, l, mid);
	query(p * 2 + 1, mid + 1, r);
}

int output[N][2];

int main() {
//	cin>>n>>q;
	n = read();
	q = read();

	rep(i, 1, n - 1) {
		output[i][0] = read();
		output[i][1] = read();
		addedge(output[i][0], output[i][1]);
		addedge(output[i][1], output[i][0]);
	}

	dfs1(1);
	dfs2(1, 1);

	rep(i, 1, q) {
		int u, v;
		u = read();
		v = read();

		while (top[u] != top[v]) {
			if (dep[top[u]] < dep[top[v]])
				swap(u, v);

//			cout << "starting upd:" << dfn[top[u]] << ' ' << dfn[u] << '\n';
//			pause;
			upd(1, 1, n, dfn[top[u]], dfn[u], i);
			u = fa[top[u]];
		}

		if (dep[u] > dep[v])
			swap(u, v);

		upd(1, 1, n, dfn[u] + 1, dfn[v], i);
//		query(1, 1, n);
//		cout << "ans:";
//
//		rep(i, 2, n) cout << ans[dfn[i]] << ' ';
//
//		endl;
//		pause;
	}

	query(1, 1, n);

	rep(i, 1, n - 1) {
		int u = output[i][0], v = output[i][1];

		if (dep[u] > dep[v]) {
			print(ans[dfn[u]]);
			putchar(' ');
		} else {
			print(ans[dfn[v]]);
			putchar(' ');
		}
	}
}