考察知识点：树上差分

问题描述

        给定一棵由 n 个节点组成的树以及 m 个不重复的无序数对（a1,b1）(a2,b2) (a3,b3)......(am,bm)，其中ai互不相同，bi互不相同。ai，bi（1 <= i,j <= m）。小明想知道是否能够选择一条树上的边砍断，使得对于每个（ai，bi）满足ai，bi不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从一开始），否则输出 -1。

输入格式

输入n + m行，第一行为两个正整数n，m。后面n - 1行，每行两个整数xi，yi表示第i条边的两个端点。后面m行，每行两个正整数ai，bi。

输出格式

一行一个整数，表示答案，如果有多个答案，输出编号最大的一个。

思路

1、按顺序输入每条边（无向边），使用邻接表储存图。

2、使用dfs方法确定每个点所处的层次，0处于第0层，以1为根节点，处于第1层。

3、输入每个数对a,b，d[a] ++，d[b] ++,求出点a与点b最近的公共祖先节点p，d[p] -= 2；

4、使用深度遍历每个点，求出每条边当前的权值，如果等于m则表示这条边可以砍掉，如果边的编号大于ans，则使用ans保存。

5、输出答案。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 101000, M = 2 * N;
int n,m;
int h[N],e[M],ne[M],idx;
int depth[N],fa[N][25];
int d[N];
int q[N];
int ans;
void add(int a,int b)
{e[idx] = b,ne[idx] = h[a], h[a] = idx ++;
}void bfs()
{memset(depth,0x3f,sizeof depth);depth[0] = 0;depth[1] = 1;queue<int> q;q.push(1);while(!q.empty()){int t = q.front();q.pop();for(int i = h[t]; ~i; i = ne[i]){int j = e[i];if(depth[j] > depth[t] + 1){depth[j] = depth[t] + 1;q.push(j);fa[j][0] = t;for(int k = 1; k <= 16; k ++)fa[j][k] = fa[fa[j][k - 1]][k - 1];}}}
}int lca(int a,int b)
{if(depth[a] < depth[b]) swap(a,b);for(int k = 16; k >= 0; k --)if(depth[fa[a][k]] >= depth[b])a = fa[a][k];if(a == b) return a;for(int k = 16; k >= 0; k --)if(fa[a][k] != fa[b][k]){a = fa[a][k];b = fa[b][k];}return fa[a][0];
}int dfs(int u,int father,int id)
{int res = d[u];for(int i = h[u]; ~i; i = ne[i]){int j = e[i];if(j == father) continue;int s = dfs(j,u,i);res += s;}if(res == m) ans = max(ans,id / 2 + 1);return res;
}int main()
{ans = -1;cin >> n >> m;memset(h,-1,sizeof h);for(int i = 0; i < n - 1; i ++){int a,b;cin >> a >> b;add(a,b),add(b,a);}bfs();for(int i = 0; i < m; i ++){int a,b;cin >> a >> b;int p = lca(a,b);d[a] ++,d[b] ++,d[p] -= 2;}dfs(1,-1,0);cout << ans << endl;return 0;
}