6. 图1-树和图
题目ID：8254必做题100分
最新提交：
Memory Limit Exceeded
0 分
历史最高：
Memory Limit Exceeded
0 分
时间限制: 1000ms
空间限制: 131072kB
题目描述
时间限制：1s 空间：128M
题目描述：
给出一个无向图，和一棵树，求至少要加多少边才能将这棵树变成给定的图，如果无法变成，则输出 𝑖𝑚𝑝𝑜𝑠𝑠𝑖𝑏𝑙𝑒impossible。
输入格式：
第一行包含两个正整数 𝑁N 和 𝑀M，表示有 𝑁N 个点，图有 𝑀M 条边。（节点编号从 11 到 𝑁N）
接下来 𝑁−1N−1 行每行包含两个正整数 𝑢,𝑣u,v，表示一条树的边。保证是一棵树。
接下来 𝑀M 行每行包含两个用空格隔开的正整数 𝑢,𝑣u,v，表示一条从 𝑢u 到 𝑣v 的无向路径。保证没有重边和自环。
输出格式：
一个整数，表示最少的边数，如果无法达成，则输出 𝑖𝑚𝑝𝑜𝑠𝑠𝑖𝑏𝑙𝑒impossible。
样例输入：
5 6
1 2
1 3
3 4
2 5
1 2
1 3
3 4
2 5
2 3
2 4
样例输出：
2
约定：
1≤𝑁≤50001≤N≤5000
1≤𝑀≤60001≤M≤6000
#include <bits/stdc++.h>
using namespace std;
int tre[5010][5010], mp[5010][5010];
int x, y, n, m, ans;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i < n; ++i)
{
cin >> x >> y;
tre[x][y] = 1;
tre[y][x] = 1;
}
for (int i = 1; i <= m; ++i)
{
cin >> x >> y;
mp[x][y] = 1;
mp[y][x] = 1;
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
if (tre[i][j] == 0 && mp[i][j] == 1)
{
++ans;
}
else if (tre[i][j] == 1 && mp[i][j] == 0)
{
cout << "impossible";
return 0;
}
}
}
cout << ans / 2;
}
