简单题。
在线很不好做，考虑离线后求出每个点第一次变黑的时间，即找到其祖先所有合法修改的时间最小值。在 dfs 过程中对每个 \(A\) 维护一个 map，遇到修改 \((x,y,t)\) 就将 \(B_x\) 的前 \(y\) 位插入 map。对节点 \(u\) 枚举 \(B_u\) 的所有前缀即可在 map 里找到与之匹配的修改。用 map 套 set 维护所有时间戳即可动态插入，删除，求最小值。
#include<bits/stdc++.h>
#define inf 2e9
using namespace std;
const int N=2e5+10;
int n,q,idx;
string a[N],b[N];
int c[N];
vector<int>G[N],ti[N];
vector<pair<int,int>> opt[N];
map<string,int> to; //to 存 A 的编号
map<string,set<int>> val[N];void dfs(int x,int fa)
{int 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 ans[2];
int que[N];
int main()
{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 que[i]=x;}dfs(1,0);for(int i=1;i<=q;i++){if(que[i]!=-1)cout<<ans[que[i]]<<"\n";elsefor(auto x:ti[i])ans[c[x]]++;}return 0;
}