第十四届蓝桥杯省赛C/C++ 大学 B 组 砍树

本题是一道LCA树上差分的题目注意本题的树上差分是边差分需要存储边的序号以及点和边的对应关系进行差分运算。树上差分可以帮助我们知道当前边被多少条路径覆盖差分数组中某点j的值为m那么则说明这条边删去后会使我们的m条边不连通。代码如下#includeiostream #includevector using namespace std; #define int long long const int N 1e5 10; vectorpairint,int g[N]; int deep[N]; int fa[N][25]; int cnt[N]; int l[N]; void dfs(int index, int index1) { deep[index] deep[index1]1; fa[index][0] index1; for (int i 1; i 20; i) { fa[index][i] fa[fa[index][i - 1]][i - 1]; } for (auto i : g[index]) { if (i.first index1) continue; l[i.first] i.second; dfs(i.first, index); } } int lca(int index, int index1) { if (deep[index] deep[index1])// swap(index, index1); for (int i 20; i 0; i--) { if (deep[index] deep[index1]) { index fa[index][i]; } } if (index index1) return index; for (int i 20; i 0; i--) { if (fa[index][i] ! fa[index1][i]) { index fa[index][i]; index1 fa[index1][i]; } } return fa[index][0]; } void dfs1(int index) { for (auto i : g[index]) { if (i.first fa[index][0]) { continue; } dfs1(i.first); cnt[l[index]] cnt[l[i.first]]; } } signed main() { int n, m; cin n m; for (int i 1; i n; i) { int x, y; cin x y; g[x].push_back({ y,i }); g[y].push_back({ x,i }); } dfs(1, 0); for (int i 1; i m; i) { int u, v; cin u v; cnt[l[u]]; cnt[l[v]]; cnt[l[lca(u, v)]] - 2; } dfs1(1); int ans -1; for (int i 1; i n; i) { if (cnt[i] m) ans i; } cout ans endl; return 0; }