已经唐到 D 题都调不出来了，AC26 WA4 RE19

考虑正攻，用 $num_u$ 维护 $u$ 号字符串是哪些字符串拼接而成，可以递归，$0$ 代表主机。注意到 $num_0$ 一直只会有一个数，特判了一下，然后忘了。

求调，或者说明这个方法不可做

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define endl "\n"
#define N 800009

int n,q,p[N];
string s[N];
int find(int x){ return p[x] == x ? x : p[x] = find(p[x]); }
vector<int> num[N];
void print(int u){
	if(num[u].size() == 0){
		cout<<s[u];
		return;
	}
	for(int i = 0;i < num[u].size();i++){
		print(num[u][i]);
	}
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>q;
    for(int i = 1;i <= n;i++) p[i] = i;
    n++;
    num[0].push_back(n);
    s[n] = "";
    while(q--){
    	int t,x;
    	string str;
    	cin>>t;
    	if(t == 1){
    		cin>>x;
    		if(num[0][0] == x) continue;
    		num[x].clear();
    		num[x].push_back(num[0][0]);
    	}
    	if(t == 2){
    		cin>>x>>str;
    		s[++n] = str;
    		num[x].push_back(n);
    	}
    	if(t == 3){
    		cin>>x;
    		num[0].clear();
    		num[0].push_back(x);
    	}
    }
    print(0); 
}