很涩的一个题。
题意
假如我们有一个 AC 自动机，我们可以取出其中的点，字符边和 Fail 边，这样其就变成了一个有 $n$ 个点和 $2n-2$ 条边的有向图。现在给出你这样一个有向图，你需要找到其原始的 AC 自动机结构（包括 1. 找到根 2. 找到哪些边是 Trie 树边 3. 给所有的 Trie 树边分配一个字符，字符集大小不限）。
$n=10^5$.
题解
Part I 找根
大力观察 AC 自动机，你发现如果只考虑其中 $u \to v, v \to u$ 这样的边，这些边一定会连成一个类菊花的结构（均是从根节点开始，按照每个字符边一路往下走到某个位置停止）或是一条链。
你只需要画出一个 AC 自动机，然后只保留那些 $u \to v, v \to u$ 的边，就可以明晰大致结构了。
如果这些双向边构成的子无向图中，有一个点度数 $\ge3$，那么他就一定为根。考虑链的时候怎么做。
如果形成了一条链，我们再对这一情况进行大力观察（建议画出一个符合结构的 AC 自动机），我们发现存在这样的一类点，满足以下三个条件：
- 这个点初始时不在链上
- 链上有一个点连向该点
- 这个点有一条边连向链上的点（易知这是 fail 边）
那么，这条 fail 边一定会连向根节点或根节点的儿子（详细说明过于繁琐，你可以自行画出 AC 自动机，找到这样的点，并尝试回答为什么）。
因此，记这个点为 $x$，我们只需要 check $x$ 以及与 $x$ 相邻的两点这三个点作为根的可能性即可。问题转化为，我们假定了一个根，如何去 check 是否存在一种合法的情况。
注意，你还需要警惕保留 $u \to v, v \to u$ 的边后出现多个连通块的情况，这显然是不合法的。
Part II 构建 AC 自动机
check 的第一步一定是根据这个根构建出 AC 自动机，这一步较为简单，从根节点开始，所有连向没有连过的点都是 Trie 树边，所有连向深度比他低的边都是 fail 边，若出现一条边连向深度相同的点，或出现一个点没有 fail 边（根节点除外） / 有超过一个 fail 边，报告无解。如果有一个点没有边连向他（根节点除外），也报告无解。
现在，我们已经找到那些边是 Trie 树边了，对于字符的分配，我们不妨将其分配在边连向的点上而并非边上。我们利用一个并查集结构。我们从根开始 bfs 遍历每个点，对于一个点 $u$，如果其 fail 连向的是 $v$，我们就把 $u,v$ 并起来，然后 $u$ 和 $v$ 再各自向其父亲跳，直至：
- $u$ 和 $v$ 已经被 merge 过了
- $v$ 到达了根
这两个条件任意满足其一即可。
然后，我们为每个并查集分配一个不同的字符，再验证对于每个点，其儿子的字符都是互不相同的。
Part III 验证 AC 自动机
现在我们已经构造好了 AC 自动机的结构，但其不一定为合法的，我们需要通过当前分配的字符集，重新跑一边 AC 自动机，验证其 fail 结构与原来构建的是否相同。问题转换为了构造字符集大小为 $O(n)$ 的 AC 自动机。
观察原来的 AC 自动机构造方法，发现时间复杂度瓶颈在于克隆 to 数组，在字符集大小为 $O(n)$ 是，将 $fail[u]$ 的 to 数组克隆到 $u$ 上需要 $O(n)$ 的时间复杂度，导致总时间复杂度来到了 $O(n^2)$。
因此，我们对于每一个点都开一个可持久化线段树，这棵线段树只需要满足两种操作，单点修改与单点查询，我们将原来访问 tr[u].to[x] 的操作变成了 query(root[u],x)，虽然修改和查询的时间复杂度由 $O(1)$ 变成了 $O(\log n)$，但是现在我们可以直接通过 root[u]=root[tr[u].fail] 来完成原来需要 $O(n)$ 完成的克隆操作。
至此，我们根据在 Part II 中得到的字符分配构建好 AC 自动机，再将其的 fail 结构与 Part II 中得到的 fail 结构一一对比即可。
总体时间复杂度为 $O(n\log n)$。
代码
代码过于狗屎，不建议查看。
#include<bits/stdc++.h>
#define pi pair<int,int>
#define mk make_pair
using namespace std;
const int N=4e5+5;
int T,n,root;
struct node{
int to,nxt;
}e[N];
int head[N],cnt;
void add(int u,int v){
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
map<pi,bool> ma;
int du[N],child[N],fa[N],ffa[N];
int find(int u){
return ffa[u]==u?(u):(ffa[u]=find(ffa[u]));
}
int dep[N];
void merge(int u,int v){
while(u!=root && v!=root){
if(find(u)==find(v)) break;
ffa[find(u)]=find(v);
u=fa[u];v=fa[v];
}
}
int col[N],fail[N];
int c[N*16][2],val[N*16],treetot,ro[N*16];
void Ins(int &p, int l, int r, int x, int y) {
int q = ++treetot;
c[q][0] = c[p][0], c[q][1] = c[p][1], val[q] = val[p], p = q;
if (l == r) return val[p] = y, void();
int mid = (l + r) >> 1;
if (x <= mid) Ins(c[p][0], l, mid, x, y);
else Ins(c[p][1], mid + 1, r, x, y);
}
int Get(int p, int l, int r, int x) {
if (l == r || !p) return val[p];
int mid = (l + r) >> 1;
if (x <= mid) return Get(c[p][0], l, mid, x);
return Get(c[p][1], mid + 1, r, x);
}
struct ACAM{
struct Trie_Tree{
int fail;
map<int,int> to;
}tr[N];
void init(){
for(int i=1;i<=treetot;i++) c[i][0]=c[i][1]=val[i]=0;
treetot=0;
for(int i=1;i<=n;i++){
tr[i].to.clear();
tr[i].fail=0;
ro[i]=0;
}
for(int u=1;u<=n;u++){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;if(v==fail[u]) continue;
tr[u].to[col[v]]=v;
}
}
}
void Get_Fail(){
queue<int> q;q.push(root);ro[root]=++treetot;
while(!q.empty()){
int u=q.front();q.pop();
if(u!=root) ro[u]=ro[tr[u].fail];
for(auto x:tr[u].to){
tr[x.second].fail=Get(ro[tr[u].fail],1,n,x.first);
Ins(ro[u],1,n,x.first,x.second);
if(tr[x.second].fail==0) tr[x.second].fail=root;
q.push(x.second);
}
}
}
}AC;
int in[N];
bool check(){
queue<int> q;q.push(root);
for(int i=1;i<=n;i++) dep[i]=fa[i]=col[i]=fail[i]=in[i]=0;
for(int i=1;i<=n;i++) ffa[i]=i;
dep[root]=1;
while(!q.empty()){
int u=q.front();q.pop();
int failcnt=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(dep[v]!=0 && dep[v]<dep[u]){
merge(u,v);fail[u]=v;
failcnt++;
}
else if(dep[u]==dep[v]){
return 0;
}
else{
q.push(v);fa[v]=u;in[v]++;
dep[v]=dep[u]+1;
}
}
if(u==root){
if(failcnt!=0) return 0;
}
else{
if(failcnt!=1) return 0;
}
}
for(int i=1;i<=n;i++){
if(i==root && in[i]!=0) return 0;
else if(i!=root && in[i]!=1) return 0;
}
int tot=0;
for(int i=1;i<=n;i++){
if(i==root) continue;
if(!col[find(i)]){
col[find(i)]=++tot;
}
col[i]=col[find(i)];
}
for(int u=1;u<=n;u++){
set<int> tmpset;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;if(v==fail[u]) continue;
if(tmpset.count(col[v])) return 0;
tmpset.insert(col[v]);
}
}
AC.init();
AC.Get_Fail();
for(int i=1;i<=n;i++){
if(AC.tr[i].fail!=fail[i]) return 0;
}
printf("Yes\n");
for(int u=1;u<=n;u++){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;if(v==fail[u]) continue;
printf("%d %d %d\n",u,v,col[v]);
}
}
return 1;
}
int lianshu;
int lianfa[N];
int lianfind(int u){
return lianfa[u]==u?u:lianfa[u]=lianfind(lianfa[u]);
}
void solve(){
scanf("%d",&n);lianshu=0;
if(n==1){
printf("Yes\n");return;
}
cnt=0;
int Root=0;
for(int i=1;i<=n;i++){
head[i]=du[i]=child[i]=0;
}
ma.clear();
for(int i=1;i<=n;i++) lianfa[i]=i;
for(int i=1,u,v;i<=2*n-2;i++){
scanf("%d%d",&u,&v);
add(u,v);ma[make_pair(u,v)]=1;
if(ma.count(make_pair(v,u))){
du[v]++;du[u]++;
if(lianfind(u)!=lianfind(v)){
lianfa[lianfind(u)]=lianfind(v);
}
}
}
int tmp=0;
for(int i=1;i<=n;i++){
if(du[i]==0) continue;
if(lianfind(i)!=tmp){
if(tmp==0) tmp=lianfind(i);
else{
printf("No\n");
return;
}
}
}
for(int i=1;i<=n;i++){
if(du[i]>=3){
if(!Root) Root=i;
else {
printf("No\n");return;
}
}
}
if(!Root){
bool allhasdu=1;
for(int u=1;u<=n;u++){
if(du[u]>0){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;if(du[v]>0) continue;
child[v]=1;
}
}
}
for(int u=1;u<=n;u++){
if(child[u] && du[u]==0){
allhasdu=0;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(du[v]>0){
for(int j=head[v];j;j=e[j].nxt){
int _v=e[j].to;
if(du[_v]>0){
root=_v;
if(check()) return;
}
}
root=v;
if(check()) return;
printf("No\n");return;
}
}
}
}
if(allhasdu){
root=1;
if(check()) return;
}
}
else{
root=Root;
if(check()) return;
}
printf("No\n");
return;
}
int main(){
scanf("%d",&T);
while(T--) solve();
return 0;
}