链式前向星解法

解题思路:
本题写一个链式前向星的写法，仅供参考

由于我们知道在一棵树上任意两个点的路径经过的边是唯一确定的因此对于每一个路径我们对路径上的边的边权加一，这里我们可以通过树上差分在O（n）复杂度内解决，一共m对因此如果说某个边被经过了m次则说明在这m条路径上每一条都需要经过这个边，又因为在树上路径的唯一性我们可以得知这个边是必须边删掉它会使得所有点对组成的路径断开。

不了解树上差分边差分算法的可以移步oiwiki网址 https://oi-wiki.org/basic/prefix-sum/

注意事项:

参考代码:

#include <bits/stdc++.h>

using namespace std;

#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0ll)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define LL long long
#define rep(i, from, to) for(ll i = from;i<to;i++)
#define rrep(i, from, to) for(ll i = from;i>to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pp pop_back
#define endl "\n"
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int mod = 1e9 + 7;
const int P = 998244353;
const int INF = 0x3f3f3f3f;
const int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

const int N = 2e5 + 10;

int e[N],ne[N],h[N],id[N],idx;
int dep[N],fa[N][21];
int n,m;
int s[N];
int ans = -1;

void add(int a ,int b , int c)
{
    e[idx] = b, id[idx] = c, ne[idx] = h[a] , h[a] = idx ++;
}

void dfs(int u , int Fa)
{
    dep[u] = dep[Fa] + 1;
    fa[u][0] = Fa;
    for(int k = 1 ; k <= 20 ; k ++)
        fa[u][k] = fa[fa[u][k-1]][k-1];
    for(int i = h[u] ; ~i ; i = ne[i])
    {
        int j = e[i];
        if(j == Fa) continue;
        dfs(j,u);
    }
}

int lca(int a , int b)
{
    if(dep[a] < dep[b]) swap(b,a);

    for(int k = 20 ; k >= 0 ; k --)
    {
        if(dep[fa[a][k]] >= dep[b])
            a = fa[a][k];
    }

    if(a == b) return b;

    for(int k = 20 ; k >= 0 ; k --)
    {
        if(fa[a][k] != fa[b][k])
        {
            a = fa[a][k];
            b = fa[b][k];
        }
    }
    return fa[a][0];
}

void dfs2(int u , int Fa)
{
    for(int i = h[u]; ~i ; i = ne[i])
    {
        int j = e[i];
        if(j == Fa) continue;
        dfs2(j,u);
        s[u] += s[j];
        if(s[j] == m) 
        {
            ans = max(ans,id[i]);
        }
    }
}

void solve()
{
    cin >> n >> m;
    memset(h,-1,sizeof h);
    for(int i = 1 ; i < n ; i ++ )
    {
        int a,b;
        cin >> a >> b;
        add(a,b,i),add(b,a,i);
    }

    dfs(1,0);

    for(int i = 0 ; i < m ; i ++)
    {
        int a, b;
        cin >> a >> b;
        s[a] ++ ;
        s[b] ++ ;
        s[lca(a,b)] -= 2 ;
    }
    dfs2(1,0);
    cout << ans ;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t--)
    solve();    

    return 0;
}