题目描述
给定一棵由 $n$ 个结点组成的树以及 $m$ 个不重复的无序数对 $(a_1, b_1), (a_2, b_2),. . . , (a_m, b_m)$,其中 $a_i$ 互不相同,$b_i$ 互不相同,$a_i \\neq b_j(1 ≤ i, j ≤ m)$。
小明想知道是否能够选择一条树上的边砍断,使得对于每个 $(a_i, b_i)$ 满足 $a_i$ 和 $b_i$ 不连通,如果可以则输出应该断掉的边的编号(编号按输入顺序从 $1$ 开始),否则输出 $\-1$。
输入格式
输入共 $n + m$ 行,第一行为两个正整数 $n,m$。
后面 $n − 1$ 行,每行两个正整数 $x_i,y_i$ 表示第 $i$ 条边的两个端点。
后面 $m$ 行,每行两个正整数 $a_i,b_i$。
输出格式
一行一个整数,表示答案,如有多个答案,输出编号最大的一个。
数据范围
对于 $30\\%$ 的数据,保证 $1 < n ≤ 1000$。
对于 $100\\%$ 的数据,保证 $1 < n ≤ 10^5$,$1 ≤ m ≤ \\frac{n}{2}$。
输入样例:
6 2
1 2
2 3
4 3
2 5
6 5
3 6
4 5
输出样例:
4
样例解释
断开第 $2$ 条边后形成两个连通块:$\{3, 4\}$,$\{1, 2, 5, 6\}$,满足 $3$ 和 $6$ 不连通,$4$ 和 $5$ 不连通。
断开第 $4$ 条边后形成两个连通块:$\{1, 2, 3, 4\}$,$\{5, 6\}$,同样满足 $3$ 和 $6$ 不连通,$4$ 和 $5$ 不连通。
$4$ 编号更大,因此答案为 $4$。
树上差分,统计每条边出现的次数,并根据编号更新答案
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = N << 1;
int h[N], e[M], w[M], ne[M], idx;
int depth[N], f[N][20];
int cnt[N];
int n, m, ans;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void init(int u, int father)
{
depth[u] = depth[father] + 1;
f[u][0] = father;
for(int i = 1;(1 << i) <= depth[u];i ++)
{
f[u][i] = f[f[u][i - 1]][i - 1];
}
for(int i = h[u];i != -1;i = ne[i])
{
int j = e[i];
if(j == father) continue;
init(j, u);
}
}
int lca(int a, int b)
{
if(depth[a] < depth[b]) swap(a, b);
for(int i = 17;i >= 0;i --)
{
if(depth[f[a][i]] >= depth[b])
{
a = f[a][i];
}
}
if(a == b) return a;
for(int i = 17;i >= 0;i --)
{
if(f[a][i] != f[b][i])
{
a = f[a][i];
b = f[b][i];
}
}
return f[a][0];
}
int dfs(int u, int father)
{
int res = cnt[u];
for(int i = h[u];i != -1;i = ne[i])
{
int j = e[i];
if(j == father) continue;
int child = dfs(j, u);
if(child == m && w[i] > ans) ans = w[i];
res += child;
}
return res;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
memset(h, -1, sizeof h);
int x, y;
for(int i = 1;i <= n - 1;i ++)
{
cin >> x >> y;
add(x, y, i), add(y, x, i);
}
init(1, 0);
for(int i = 1;i <= m;i ++)
{
cin >> x >> y;
cnt[x] ++, cnt[y] ++, cnt[lca(x, y)] -= 2;
}
ans = -1;
dfs(1, 0);
cout << ans << endl;
return 0;
}