深度优先搜索实战：蓝桥杯比赛中的砍树问题（图的存储、树上差分与LCA）解析——第二部分：暴力解法

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;

typedef pair<int,int> pii;

vector<int>edge[N];

int n, m;

int w[N];//从每一个边的边权。

map<pii, int>id;//存边的编号

//s是路径的起点，v是路径的重终点，u表示你当前走到了哪个点。
bool dfs(int s, int u, int father, int v)
{
	if(u == v)
	{
		return true;
	}


	for(int i = 0; i < edge[u].size(); i ++)
	{
		int son = edge[u][i];

		if(son == father)
			continue;

		if(dfs(s, son, u, v))
		{
			int ID = id[{u, son}];
			w[ID] ++;
			return true;
		}
	}

	return false;
}

void solve()
{
	cin >> n >> m;
	for(int i = 0; i < n - 1; i ++)
	{
		int x, y; cin >> x >> y;

		edge[x].push_back(y);
		edge[y].push_back(x);
		
		id[{x, y}] = id[{y, x}] = i;
	}

	for(int i = 0; i < m; i ++)
	{
		int x, y; cin >> x >> y;
		dfs(x, x, -1, y);
	}

	int ans = -1;
	for(int i = n - 1; i >= 0; i --)
	{
		if(w[i] == m)
		{
			ans = i + 1;
			break;
		}
	}

	cout << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	// cin >> t;
	while(t--)
	solve();
}