解题思路:
dfs,也就是深度优先搜索
注意事项:
有一个测试样例是错的,输入内容如下:
4 2 49868141 62921933 1 1 49868141 62921933 1 2 3 1 1 2
可以看到这个测试样例缺少一行输入,故这段代码只能在这个判题平台上拿到91分。
参考代码:
#include <bits/stdc++.h> #define int long long//其实上面那个样例好像是想卡longlong来着,没这句就会从“运行错误”变成“答案错误”。。。 using namespace std; int ans = 0;//答案 vector<int> weight1, weight2;//两棵树的各节点权值 vector<vector<int>> adj1, adj2;//两棵树的邻接表,存储树的结构 //dfs函数。node1为第一个树的被搜索结点,node1parent为其父结点。depth是dfs搜索深度,adj1为树1邻接表,weight1为树1各结点权值。 int dfs(int node1, int node1parent, int node2, int node2parent, int depth, vector<vector<int>>& adj1, vector<vector<int>>& adj2, vector<int>& weight1, vector<int>& weight2) { ans = max(ans, depth);//更新答案 map<int, int>mp;//建立一个树1的,权值到节点的映射mp //遍历树1的node1结点的子节点 for (const auto& n : adj1[node1]) { if (n != node1parent)//排除父结点 { mp[weight1[n]] = n;//联系权值与子结点 } } //遍历树2的node2结点的子结点 for (const auto& n : adj2[node2]) { if (n != node2parent)//排除父结点 { if (mp.count(weight2[n]) != 0)//如果在树1的node1的子节点中找到了和树2的node2的子节点权值相等的子结点,就继续递归dfs搜索下去 { //更新答案。其中,mp[weight2[n]]是与树2结点node2的子节点n相同权值的树1子节点。两个父节点则为现在所搜索的结点node1和node2。深度记得+1 ans = max(ans, dfs(mp[weight2[n]], node1, n, node2, depth + 1, adj1, adj2, weight1, weight2)); } } } return ans; } signed main()//一定是signed而不是int,因为我们上面的define把int定义为了longlong,而longlong不能作为返回值类型 { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; weight1.resize(n+5); weight2.resize(m+5); adj1.resize(n + 10); adj2.resize(m + 10); for (int i = 1; i <= n; i++) { cin >> weight1[i]; } for (int i = 1; i <= m; i++) { cin >> weight2[i]; } int u, v, p, q; for (int i = 1; i <= n - 1; i++) { cin >> u >> v; adj1[u].push_back(v); adj1[v].push_back(u); } for (int i = 1; i <= m - 1; i++) { cin >> p >> q; adj2[q].push_back(p); adj2[p].push_back(q); } if(weight1[1]!=weight2[1])//如果根节点不相同,说明最长共同前缀是0 { cout << "0"; } else { //如果根节点相同则开始dfs搜索 cout << dfs(1, 0, 1, 0, 1, adj1, adj2, weight1, weight2); } }
以防你真的很想ac:我找到一段能在这个平台ac的代码,但我不知道为什么它能在这个平台ac。我在本地测试上面那个测试样例的时候也过不了,但它就是能ac。关键可能出现在主函数,但我不想去折腾了。
#include <bits/stdc++.h> #define int long long #define endl '\n' using namespace std; int mmax = 0; int dfs(int fn, int pn, int fm, int pm, int dep, const vector<int>& c, const vector<int>& d, const vector<vector<int>>& G, const vector<vector<int>>& T) { mmax = max(mmax, dep); map<int, int> mp; for (auto t1 : G[fn]) { if (t1 != pn) { mp[c[t1]] = t1; / } } for (auto t2 : T[fm]) { if (t2 != pm) { if (mp.count(d[t2]) != 0) { mmax = max(mmax, dfs(mp[d[t2]], fn, t2, fm, dep + 1, c, d, G, T)); } } } return mmax; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> weight1(n + 5), weight2(m + 5); for (int i = 1; i <= n; i++) { cin >> weight1[i]; } for (int i = 1; i <= m; i++) { cin >> weight2[i]; } vector<vector<int>> tree1(n + 5), tree2(m + 5); for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; tree1[u].push_back(v); tree1[v].push_back(u); } for (int i = 1; i < m; i++) { int u, v; cin >> u >> v; tree2[u].push_back(v); tree2[v].push_back(u); } if (weight1[1] != weight2[1]) { cout << 0 << endl; } else { int res = dfs(1, 0, 1, 0, 1, weight1, weight2, tree1, tree2); cout << res << endl; } return 0; }
0.0分
1 人评分
母牛的故事 (C语言代码)浏览:709 |
C语言程序设计教程(第三版)课后习题5.8 (C语言代码)浏览:609 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:578 |
WU-蓝桥杯算法提高VIP-企业奖金发放 (C++代码)浏览:1246 |
WU-小九九 (C++代码)浏览:1711 |
C语言程序设计教程(第三版)课后习题6.2 (C语言代码)浏览:716 |
简单的a+b (C语言代码)浏览:876 |
简单的a+b (C语言代码)浏览:572 |
1035 题解浏览:872 |
C二级辅导-分段函数 (C语言代码)浏览:656 |