[NTUJ] 2584. Interesting Trees

題目連結:http://acm.csie.org/ntujudge/problem.php?id=2584

---

在兩棵樹上找LCS，其實跟原本找LCS的方法一樣，因為他還是可以找到字串的上一個字元，只不過原本的是要看前一個字元就好，這變成要看父親的字元，狀態也稍微改動成$dp[i][j]$是第一顆樹的0~i跟第二顆樹的0~j的LCS長度

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
typedef pair<int,int> PII;
#define FF first
#define SS second

const int N = 1000 + 5;

string s1, s2;
vector<int> G1[N], G2[N];
int dp[N][N], ans;
void DFS(int,int,int,int);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int t; cin>>t;
	while(t--){
		ans=0;
		int n, m; cin>>n>>m;
		for(int i=1;i<=n;i++) G1[i].clear();
		for(int i=1;i<=m;i++) G2[i].clear();
		cin>>s1;
		for(int i=0;i<n-1;i++){
			int u, v; cin>>u>>v;
			G1[u].PB(v);
			G1[v].PB(u);
		}
		cin>>s2;
		for(int i=0;i<m-1;i++){
			int u, v; cin>>u>>v;
			G2[u].PB(v);
			G2[v].PB(u);
		}
		queue<PII> BFS;
		BFS.push({1, 0});
		while(!BFS.empty()){
			PII u = BFS.front();BFS.pop();
			for(auto v:G1[u.FF])
				if(v != u.SS) BFS.push({v,u.FF});
			DFS(u.FF, u.SS, 1, 0);
		}
		cout<<ans<<'\n';
	}
	return 0;
}

void DFS(int i, int i1, int j, int j1){
	if(s1[i-1]==s2[j-1]) dp[i][j] = dp[i1][j1]+1;
	else dp[i][j] = max(dp[i][j1], dp[i1][j]);
	ans = max(ans, dp[i][j]);
	for(auto v:G2[j]) if(v!=j1)
		DFS(i, i1, v, j);
}