记录编号	618143	评测结果	AAAAAAAAAA
题目名称	4445.饭团	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	8.905 s
提交时间	2026-08-27 09:58:34	内存使用	11.80 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int p[N], dfn[N], rk[N], cnt, sz[N];
int l[N], r[N], pt[N], n;
vector<int> G[N];
void clear() {
	for (int i = 1; i <= n; i++) {
		G[i].clear();
		l[i] = r[i] = pt[i] = 0;
		p[i] = dfn[i] = rk[i] = sz[i] = 0;
	}
	cnt = 0;
}
void add(int x, int y) {
	G[x].push_back(y);
}
void dfs(int x, int fa) {
	rk[dfn[x] = ++cnt] = x;
	sz[x] = 1;
	for (auto y : G[x]) {
		if (y == fa) continue;
		dfs(y, x);
		sz[x] += sz[y];
	}
	return;
}
void solve(int x, int y, int a, int b) {
	if (a > b || x > y) return;
	if (a == b) {
		for (int i = x; i <= y; i++) {
			cout << "=" << p[i];
		}
	} else {
		int mid = (a + b) >> 1, lt = x, rt = y;
		vector<int> tmp; tmp.clear();
		for (int i = x; i <= y; i++) {
			if (l[p[i]] <= mid && r[p[i]] > mid) {
				tmp.push_back(p[i]);
			} else if (r[p[i]] <= mid) {
				pt[lt++] = p[i];
			} else {
				pt[rt--] = p[i];
			}
		}
		sort(tmp.begin(), tmp.end(), [&](int u, int v) {
			return l[u] < l[v];
		});
		int lp = a, rp = b;
		for (auto v : tmp) {
			while (lp < l[v]) cout << "+" << rk[lp], lp++;
			while (rp > r[v]) cout << "+" << rk[rp], rp--;
			cout << "=" << v;
		}
		while (lp > a) cout << "-", lp--;
		while (rp < b) cout << "-", rp++;
		for (int i = rt + 1; i <= y; i++) p[i] = pt[i], pt[i] = 0;
		for (int i = x; i <= lt - 1; i++) p[i] = pt[i], pt[i] = 0;
		if (rt + 1 <= y) {
			for (int i = a; i <= mid; i++) cout << "+" << rk[i];
			solve(rt + 1, y, mid + 1, b);
			for (int i = a; i <= mid; i++) cout << "-";
		}
		if (x <= lt - 1) {
			for (int i = mid + 1; i <= b; i++) cout << "+" << rk[i];
			solve(x, lt - 1, a, mid);
			for (int i = mid + 1; i <= b; i++) cout << "-";
		}
	}
}
int main() {
	freopen("riceball.in", "r", stdin);
	freopen("riceball.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T; cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 2, u, v; i <= n; i++) {
			cin >> u >> v;
			add(u, v), add(v, u);
		}
		dfs(1, 0); 
		for (int i = 1; i <= n; i++) {
			l[i] = dfn[i], r[i] = dfn[i] + sz[i] - 1;
			p[i] = i; 
		}
		solve(1, n, 1, n);
		cout << "!" << '\n';
		clear();
	}
	return 0;
}