int n, m, idx;string s;int head[maxn];pii st[maxn], ed[maxn], ans;struct Edge {int to, nxt; char c;} edge[maxn * 2];void addedge(int u, int v, char c) {edge[idx] = {v, head[u], c};head[u] = idx ++;edge[idx] = {u, head[v], c};head[v] = idx ++;}void dfs(int u, int fa) {st[u] = ed[u] = {0, u};for(int i = head[u]; ~i; i = edge[i].nxt) {int v = edge[i].to; char c = edge[i].c;if(v == fa) continue;dfs(v, u);if(c == s[st[v].x + 1] && st[v].x < m) st[v].x ++;if(c == s[m - ed[v].x] && ed[v].x < m) ed[v].x ++;// 路径不重复if(st[u].x + ed[v].x >= m) ans = {st[u].y, ed[v].y};if(ed[u].x + st[v].x >= m) ans = {st[v].y, ed[u].y};st[u] = max(st[u], st[v]);ed[u] = max(ed[u], ed[v]);}}int main() {ios;cin >> n >> m;for(int i = 1; i <= n; i ++) head[i] = -1;for(int i = 1; i < n; i ++) {int u, v; char c;cin >> u >> v >> c;addedge(u, v, c);}cin >> s;s = "?" + s;ans = {-1, -1};dfs(1, 0);cout << ans.x << " " << ans.y;}
经验总结扩展阅读
- 车上的winter是什么意思？
- in winter和in the winter的区别
- royalwinter是什么牌子的轮胎？
- winter什么意思中文 winter中文意思是什么
- 经典语录生活励志英文