90 lines
2.5 KiB
C++
90 lines
2.5 KiB
C++
// lanqiao3517 砍树(LCA+树上差分)
|
||
#include<bits/stdc++.h>
|
||
using namespace std;
|
||
const int N = 5e5 + 10;
|
||
// 链式前向量存储图
|
||
int edges[N], next_edge[N], head[N], edge_idx;
|
||
int fa[N][25], depth[N], subtree_pairs[N];
|
||
int n, m;
|
||
// 添加一条边
|
||
void addEdge(int s, int t){
|
||
edges[edge_idx] = t;
|
||
next_edge[edge_idx] = head[s];
|
||
head[s] = edge_idx++;
|
||
}
|
||
// 深度搜索优先并记录每个节点的深度与祖先信息
|
||
void dfs(int cur, int parent, int dep){
|
||
fa[cur][0] = parent;
|
||
depth[cur] = dep;
|
||
for(int i = 1; i <= 20; i++){
|
||
fa[cur][i] = fa[fa[cur][i-1]][i-1]; // 动态规划处理快速求最近
|
||
}
|
||
for(int i = head[cur]; i != -1; i = next_edge[i]){
|
||
int child = edges[i];
|
||
if(child == parent) continue;
|
||
dfs(child, cur, dep + 1);
|
||
}
|
||
}
|
||
int LCA(int x, int y){
|
||
if(depth[x] < depth[y]) swap(x, y);
|
||
// 将x向上跳到与y同一深度或更浅的位置
|
||
for(int i = 20; i >= 0; i--){
|
||
if(depth[fa[x][i]] >= depth[y]){
|
||
x = fa[x][i];
|
||
}
|
||
}
|
||
if(x == y) return x;
|
||
for(int i = 20; i >= 0; i--){
|
||
if(fa[x][i] != fa[y][i]){
|
||
x = fa[x][i];
|
||
y = fa[y][i];
|
||
}
|
||
}
|
||
return fa[x][0]; // 返回最近公共祖先
|
||
}
|
||
void updateSubtreePairs(int cur, int parent, int edgeId, int& maxEdgeId){
|
||
for(int i = head[cur]; i != -1; i = next_edge[i]){
|
||
int child = edges[i];
|
||
if(child == parent) continue;
|
||
updateSubtreePairs(child, cur, i, maxEdgeId); // 递归更新子节点
|
||
subtree_pairs[cur] += subtree_pairs[child];
|
||
}
|
||
// 当前节点及其子树内包含m对点对时，更新答案
|
||
if(subtree_pairs[cur] == m){
|
||
maxEdgeId = max(maxEdgeId, edgeId / 2 + 1); // 边的编号减半(因为是无向图, 一条边有两个方向的编号)
|
||
}
|
||
}
|
||
int main(){
|
||
cin >> n >> m;
|
||
// 初始化邻接表
|
||
for(int i = 1; i <= n; i++) head[i] = -1;
|
||
// 读入树的边并建立邻接表
|
||
for(int i = 1; i < n; i++){
|
||
int u, v;
|
||
cin >> u >> v;
|
||
addEdge(u, v); addEdge(v, u);
|
||
}
|
||
// 深度优先搜索预处理节点深度与祖先信息
|
||
dfs(1, 0, 1);
|
||
for(int i = 1; i <= m; i++){
|
||
int firstNode, secondNode;
|
||
cin >> firstNode >> secondNode;
|
||
subtree_pairs[firstNode]++;
|
||
subtree_pairs[secondNode]++;
|
||
subtree_pairs[LCA(firstNode, secondNode)] -= 2;
|
||
}
|
||
int ans = -1;
|
||
updateSubtreePairs(1, 0, 0, ans);
|
||
cout << ans;
|
||
return 0;
|
||
}
|
||
/* test samples -> 4
|
||
6 2
|
||
1 2
|
||
2 3
|
||
4 3
|
||
2 5
|
||
6 5
|
||
3 6
|
||
4 5
|
||
*/ |