【题目来源】
洛谷：[P3128 USACO15DEC] Max Flow P - 洛谷
【题目描述】
FJ 给他的牛棚的 \(N\) 个隔间之间安装了 \(N−1\) 根管道，隔间编号从 \(1\) 到 \(N\)。所有隔间都被管道连通了。
FJ 有 \(K\) 条运输牛奶的路线，第 \(i\) 条路线从隔间 \(s_i\) 运输到隔间 \(t_i\)。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。
【输入】
第一行输入两个整数 \(N\) 和 \(K\)。
接下来 \(N−1\) 行每行输入两个整数 \(x\) 和 \(y\)，其中 \(x\neq y\)。表示一根在牛棚 \(x\) 和 \(y\) 之间的管道。
接下来 \(K\) 行每行两个整数 \(s\) 和 \(t\)，描述一条从 \(s\) 到 \(t\) 的运输牛奶的路线。
【输出】
一个整数，表示压力最大的隔间的压力是多少。
【输入样例】
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4
【输出样例】
9
【算法标签】
《洛谷 P3128 Max Flow》 #最近公共祖先,LCA# #树链剖分# #栈# #USACO# #2015#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 50005, M = 2 * N; // N: 最大节点数, M: 最大边数
int n, k, ans; // n: 节点数, k: 查询次数, ans: 最终结果
int power[N]; // 存储每个节点的权值
int h[N], to[M], ne[M], tot; // 链式前向星存储树结构
int dep[N], fa[N][22]; // dep: 节点深度, fa: 倍增数组// 添加边到链式前向星
void add(int x, int y)
{to[++tot] = y; // 存储终点ne[tot] = h[x]; // 存储下一条边h[x] = tot; // 更新头指针
}// 深度优先搜索预处理倍增信息
void dfs(int u, int f)
{dep[u] = dep[f] + 1; // 计算节点深度fa[u][0] = f; // 直接父节点// 预处理倍增数组for (int i = 1; i <= 20; i++)fa[u][i] = fa[fa[u][i - 1]][i - 1]; // 计算2^i级祖先// 遍历所有子节点for (int i = h[u]; i; i = ne[i]){int v = to[i];if (v == f) continue; // 跳过父节点dfs(v, u); // 递归处理子节点}
}// 倍增法求最近公共祖先
int lca(int u, int v)
{// 保证u是较深的节点if (dep[u] < dep[v]) swap(u, v);// 将u提升到与v相同深度for (int i = 20; i >= 0; i--)if (dep[fa[u][i]] >= dep[v])u = fa[u][i];if (u == v) return v; // 如果已经是同一个节点// 同时向上跳跃寻找LCAfor (int i = 20; i >= 0; i--)if (fa[u][i] != fa[v][i])u = fa[u][i], v = fa[v][i];return fa[u][0]; // 返回LCA
}// 深度优先搜索统计答案
void dfs2(int u, int f)
{// 遍历所有子节点for (int i = h[u]; i; i = ne[i]){int v = to[i];if (v == f) continue; // 跳过父节点dfs2(v, u); // 递归处理子节点power[u] += power[v]; // 累加子节点的权值}ans = max(ans, power[u]); // 更新最大值
}int main()
{// 输入树结构和查询次数cin >> n >> k;// 构建树结构for (int i = 1; i < n; i++){int x, y;cin >> x >> y;add(x, y); // 无向图添加双向边add(y, x);}// 预处理倍增信息dfs(1, 0);// 处理每个查询for (int i = 1; i <= k; i++){int x, y;cin >> x >> y;int l = lca(x, y); // 求LCA// 树上差分操作++power[x]; // 起点+1++power[y]; // 终点+1--power[l]; // LCA-1--power[fa[l][0]]; // LCA的父节点-1}// 统计最终答案dfs2(1, 0);// 输出结果cout << ans << endl;return 0;
}
【运行结果】
5 10
3 4
1 5
4 2
5 4
5 4
5 4
3 5
4 3
4 3
1 3
3 5
5 4
1 5
3 4
9