[蓝桥杯]真题讲解：砍树（DFS遍历、图的存储、树上差分与LCA）

本文主要是介绍[蓝桥杯]真题讲解：砍树（DFS遍历、图的存储、树上差分与LCA），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

[蓝桥杯]真题讲解：砍树（DFS遍历、图的存储、树上差分与LCA

一、视频讲解
二、暴力代码
三、正解代码

一、视频讲解

视频讲解
在这里插入图片描述

二、暴力代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 10;typedef pair<int,int> pii;vector<int>edge[N];int n, m;int w[N];//从每一个边的边权。map<pii, int>id;//存边的编号//s是路径的起点，v是路径的重终点，u表示你当前走到了哪个点。
bool dfs(int s, int u, int father, int v)
{if(u == v){return true;}for(int i = 0; i < edge[u].size(); i ++){int son = edge[u][i];if(son == father)continue;if(dfs(s, son, u, v)){int ID = id[{u, son}];w[ID] ++;return true;}}return false;
}void solve()
{cin >> n >> m;for(int i = 0; i < n - 1; i ++){int x, y; cin >> x >> y;edge[x].push_back(y);edge[y].push_back(x);id[{x, y}] = id[{y, x}] = i;}for(int i = 0; i < m; i ++){int x, y; cin >> x >> y;dfs(x, x, -1, y);}int ans = -1;for(int i = n - 1; i >= 0; i --){if(w[i] == m){ans = i + 1;break;}}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;// cin >> t;while(t--)solve();
}

三、正解代码

//砍树：树上差分 + 最近公共祖先
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
int n, m;
int w[N];//记录每个点的点权。map<pii,int>id;
vector<int>edge[N];int siz[N], dep[N], fa[N], son[N], top[N];void dfs1(int u, int father)
{siz[u] = 1, dep[u] = dep[father] + 1;fa[u] = father;for(int i = 0; i < edge[u].size(); i ++){int s = edge[u][i];if(s == fa[u])continue;dfs1(s, u);siz[u] += siz[s];if(siz[son[u]] < siz[s])son[u] = s;}
}void dfs2(int u, int t)
{top[u] = t;if(son[u] == 0)return;dfs2(son[u], t);for(int i = 0; i < edge[u].size(); i ++){int s = edge[u][i];if(s == fa[u] || s == son[u])continue;dfs2(s, s);}
}int lca(int x, int y)
{while(top[x] != top[y]){if(dep[top[x]] < dep[top[y]])swap(x, y);x = fa[dep[x]];}return dep[x] < dep[y] ? x : y;
}void cal_sum(int u, int father)
{for(int i = 0; i < edge[u].size(); i ++){int son = edge[u][i];if(son == father)continue;cal_sum(son, u);w[u] += w[son];}
}void solve()
{cin >> n >> m;for(int i = 1; i <= n - 1; i ++){int x, y; cin >> x >> y;edge[x].push_back(y);edge[y].push_back(x);id[{x, y}] = i;id[{y, x}] = i;}	dfs1(1, 0);dfs2(1, 1);for(int i = 0; i < m; i ++){int a, b; cin >> a >> b;//做树上差分w[a] ++, w[b] ++;w[lca(a, b)] -= 2;}cal_sum(1, 0);int ans = -1;for(int i = 1; i <= n; i ++){if(w[i] == m){int ID = id[{i, fa[i]}];ans = max(ans, ID);}}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);int t = 1;// cin >> t;while(t--)solve();
}