括号与树

题目背景

本题原题为交互题，且需要“双次运行”。为了便于在 Hydro OJ 上评测，这里改造成提交函数题：选手不需要处理交互协议，也不需要自己写 main，只需要实现头文件 trees.h 中声明的两个函数。

std::string encode(std::vector<std::string> trees);
std::vector<std::string> decode(std::string tree);

评测器会在同一次运行中多次调用这两个函数，模拟原题的第一次运行与第二次运行。

题目描述

本题讨论的是无序根树。无序根树由一个根和若干个子树组成，根的儿子之间没有顺序之分。也就是说，如果两棵根树只是在某些结点处交换了儿子的排列顺序，它们仍被认为是同一棵树。

每棵无序根树可以用一段正确括号序列表示：

• 只有一个结点的树表示为 ()；
• 如果根的若干棵子树分别可以表示为 $s_1,s_2,\ldots,s_k$，那么整棵树可以表示为

其中 $p$ 可以是 $1\ldots k$ 的任意排列。由于儿子无序，同一棵树可能有多种括号表示。

现在给定一列树 $u_1,u_2,\ldots,u_n$，你需要设计一种方法，将这一列树编码成一棵树 $w$；之后，给你任意一个表示同一棵树 $w$ 的括号序列，你仍然要能够恢复出原来的树列 $u_1,u_2,\ldots,u_n$，顺序也必须一致。

需要实现的函数

encode

std::string encode(std::vector<std::string> trees);

参数 trees 中包含 $n$ 个正确括号序列，第 $i$ 个序列表示原来的第 $i$ 棵无序根树。

你需要返回一个正确括号序列，表示一棵编码树 $w$。

decode

std::vector<std::string> decode(std::string tree);

参数 tree 是一段正确括号序列，它表示的无序根树与 encode 返回的编码树 $w$ 同构，但儿子的排列顺序可能被任意打乱。

你需要返回若干个正确括号序列，依次表示最初输入给 encode 的树列。

返回的每个括号序列只需要表示与原树同构的树，不要求与原输入字符串完全相同。

约束与评分

设一个测试组中某个数据集的原始输入总长度为

encode 输出的长度为 $m$。

每个测试点最多包含 $100$ 个数据集，总 $s$ 不超过 $10^6$。评测器会检查：

1. encode 返回的是合法的正确括号序列；
2. 输出长度满足对应子任务的限制；
3. decode 能从原样编码树恢复原序列；
4. 除第 1 组外，decode 还必须能从儿子顺序被重排后的同构编码树中恢复原序列。

子任务如下：

第 4～7 组的部分分规则已写入 checker，分数会随 encode 输出长度变短而提高。

提交说明

选手提交的 C++ 文件中应包含：

#include "trees.h"
#include <bits/stdc++.h>
using namespace std;

string encode(vector<string> trees) {
    // your code
}

vector<string> decode(string tree) {
    // your code
}

不要写 main 函数。评测时会由 grader.cpp 调用你的两个函数。

样例说明

本改造版为函数题，样例不再对应普通标准输入输出。可以参考原题样例理解树的括号编码方式。