Description
You are given a tree T consisting of n vertices and n?1 edges. Each edge of the tree is associated with a lowercase English letter ci. You are given a string s consisting of lowercase English letters. Your task is to nd a simple path in the tree such that the string formed by concatenation of letters associated with edges of this path contains string s as a subsequence, or determine that there exists no such simple path.
The rst line of input contains two positive integers n and m (2≤n≤5×105,1≤m≤n?1), the number of vertices in the tree and the length of the string s. The following n?1 lines contain triples ui,vi,ci (1≤ui,vi≤n,ui≠vi,ci is a lowercase English letter), denoting an edge (ui,vi) associated with letter ci. The last line contains a string s (∣s∣=m) consisting of lowercase English letters.
Output
If the desired path exists, output its endpoints a and b. Otherwise, output -1 -1. If there are several possible answers, you are allowed to output any of them.
題意
給定 G = (V, E) , |E| = |V|-1 的樹(shù)。樹(shù)上直接相連兩點(diǎn)間的邊上記錄一個(gè)字符 ci 。樹(shù)上 a 點(diǎn)到 b 點(diǎn)的路徑經(jīng)過(guò)的邊構(gòu)成一個(gè)字符串，假設(shè)為 T 。問(wèn)給定一個(gè)長(zhǎng)為 m 的字符串 S ，S 能否成為某個(gè) T 的子序列，如果可以，給出構(gòu)成 T 串的兩個(gè)端點(diǎn) a b。否則輸出 -1 -1 。
分析
貌似已經(jīng)搞不清此題的算法，感覺(jué)算是樹(shù)分治的問(wèn)題，但又有最優(yōu)化問(wèn)題的思想。
此題的關(guān)鍵在于維護(hù)以某點(diǎn)為根的子樹(shù)的最優(yōu)狀態(tài)。
dp[i].lenl 表示以點(diǎn) i 為根的子樹(shù)最長(zhǎng)已經(jīng)匹配了 S 串的串首 lenl 個(gè)元素，同時(shí)匹配這 lenl 個(gè)元素的起始點(diǎn)為 idxl 。
dp[i].lenr 表示以點(diǎn) i 為根的子樹(shù)最長(zhǎng)已經(jīng)匹配了 S 串的串尾 lenr 個(gè)元素，同時(shí)匹配這 lenr 個(gè)元素的結(jié)束點(diǎn)為 idxr 。
任意取一個(gè)點(diǎn)作為樹(shù)的根，跑一遍 dfs 。若在某點(diǎn)最終 dp[i].lenl + dp[i].lenr >= m 且取到這么多元素不止點(diǎn) i 的同一子樹(shù)內(nèi)，則有解。
代碼
#include<bits/stdc++.h>using namespace std;const int maxn = 5e5 + 10;int n, m;char ch, s[maxn];vector< pair<int, char> > g[maxn];struct Node{ int lenl, lenr, idxl, idxr;}dp[maxn];bool dfs(int rt, int fa){ for(int i=0, to;i<g[rt].size();i++) { to = g[rt][i].first; if(to == fa) continue; if(dfs(to, rt)) return true; int tmpl = s[ dp[to].lenl + 1 ] == g[rt][i].second ? dp[to].lenl+1 : dp[to].lenl; int tmPR = s[ m - dp[to].lenr ] == g[rt][i].second ? dp[to].lenr+1 : dp[to].lenr; if(tmpl + dp[rt].lenr >= m) { printf("%d %d",dp[to].idxl, dp[rt].idxr); return true; } if(tmpr + dp[rt].lenl >= m) { printf("%d %d",dp[rt].idxl, dp[to].idxr); return true; } if(tmpl > dp[rt].lenl) { dp[rt].lenl = tmpl; dp[rt].idxl = dp[to].idxl; } if(tmpr > dp[rt].lenr) { dp[rt].lenr = tmpr; dp[rt].idxr = dp[to].idxr; } } return false;}int main(){ scanf("%d %d",&n,&m); for(int i=1, u, v;i<n;i++) { scanf("%d %d %c",&u,&v,&ch); dp[i].lenl = dp[i].lenr = 0; dp[i].idxl = dp[i].idxr = i; g[u].push_back(make_pair(v, ch)); g[v].push_back(make_pair(u, ch)); } dp[n].lenl = dp[n].lenr = 0, dp[n].idxl = dp[n].idxr = n; scanf(" %s",s+1); if(!dfs(1, -1)) printf("-1 -1");}
