在线很不好做，考虑离线后求出每个点第一次变黑的时间，即找到其祖先所有合法修改的时间最小值。

在

dfs

class="language-cpp">#include<bits/stdc++.h>

#define

vector<pair<int,int>>

opt[N];

map<string,set<int>>

val[N];void

tim=inf,ver=to[a[x]];if(!opt[x].empty())for(auto

[w,ti]:opt[x]){if(w>(int)b[x].size())continue;string

p=b[x].substr(0,w);val[ver][p].insert(ti);}for(auto

y:G[x])if(y!=fa)dfs(y,x);string

t="";for(int

w=0;w<=(int)b[x].size();w++){if(val[ver].find(t)!=val[ver].end()&&!val[ver][t].empty())tim=min((*val[ver][t].begin()),tim);if(w<(int)b[x].size())t+=b[x][w];}if(!opt[x].empty())for(auto

[w,ti]:opt[x]){if(w>(int)b[x].size())continue;string

p=b[x].substr(0,min(w,(int)b[x].size()));val[ver][p].erase(ti);}if(tim!=inf)ti[tim].emplace_back(x);

int

{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>q;for(int

i=1;i<=n;i++){cin>>a[i]>>b[i]>>c[i];if(to.find(a[i])==to.end())to[a[i]]=++idx;}for(int

i=1;i<n;i++){int

u,v;cin>>u>>v;G[u].emplace_back(v);G[v].emplace_back(u);}for(int

i=1;i<=q;i++){que[i]=-1;string

o;int

x,y;cin>>o>>x;if(o=="solve")cin>>y,opt[x].emplace_back(make_pair(y,i));else

i=1;i<=q;i++){if(que[i]!=-1)cout<<ans[que[i]]<<"\n";elsefor(auto