实际上还可保留每个节点与2的幂次祖先节点之间的节点区间信息，如果相邻区间信息的可合。那么只需$O(logn)$次合并，便可得到树上任意两点之间的区间信息。例如：任意两点间的距离，任意两点间的最大子段和（通过维护区间的最大前缀和、最大后缀和、总和以及最大子段和）。
#define N 100005
std::vector<int> g[N];
// 默认不存在的节点编号是0
int fa[N][31], dep[N];
// dfs，用来为 lca 算法做准备。接受两个参数：dfs 起始节点和它的父亲节点。
void dfs(int u, int fno) {
// 初始化：第 2^0 = 1 个祖先就是它的父亲节点，dep 也比父亲节点多 1。
fa[u][0] = fno;
dep[u] = dep[fa[u][0]] + 1;
// 初始化：其他的祖先节点：第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第
// 2^(i-1) 的祖先节点。
for (int i = 1; i < 31; ++i) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
// 遍历子节点来进行 dfs。
for (int v : g[u]) {
if (v == fno)
continue;
dfs(v, u);
}
}
// lca。用倍增算法算取 x 和 y 的 lca 节点。
int lca(int x, int y) {
// 令 y 比 x 深。
if (dep[x] > dep[y])
swap(x, y);
// 令 y 和 x 在一个深度。
int tmp = dep[y] - dep[x];
for (int j = 0; tmp; ++j, tmp >>= 1)
if (tmp & 1)
y = fa[y][j];
// 如果这个时候 y = x，那么 x，y 就都是它们自己的祖先。
if (y == x)
return x;
// 不然的话，找到第一个不是它们祖先的两个点。
for (int j = 30; j >= 0 && y != x; --j) {
if (fa[x][j] != fa[y][j]) {
x = fa[x][j];
y = fa[y][j];
}
}
// 返回结果。
return fa[x][0];
}
void add(int x, int y) {
g[x].push_back(y);
g[y].push_back(x);
}
// 注意初始时以0作为根节点的父亲，dfs(u,0)
一棵树，树的节点有权值，求树上任意两节点之间的最大子段和https://codeforces.com/contest/1843/problem/F2
#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 200005
#define LG 31
#define MOD 998244353
using namespace std;
std::vector<int> g[N];
int fa[N][LG], dep[N];
struct Info {
int sum, max_prf, min_prf, max_suf, min_suf, max_seg, min_seg;
Info(int val = 0) {
sum = val;
max_prf = max_suf = max_seg = max(0, val);
min_prf = min_suf = min_seg = min(0, val);
}
Info operator+(const Info& o) {
Info rt(0);
rt.sum = sum + o.sum;
rt.min_prf = min(min_prf, sum + o.min_prf);
rt.max_prf = max(max_prf, sum + o.max_prf);
rt.min_suf = min(o.min_suf, o.sum + min_suf);
rt.max_suf = max(o.max_suf, o.sum + max_suf);
rt.min_seg = min({min_suf + o.min_prf, min_seg, o.min_seg});
rt.max_seg = max({max_suf + o.max_prf, max_seg, o.max_seg});
return rt;
}
} info[N][LG];
// fa[i][j] i节点的第2^j个祖先
// info[i][j] 在i节点的第2^j个祖先（不包含f[i][j]）到当前的节点i的区间信息。
// dfs，用来为 lca 算法做准备。接受两个参数：dfs 起始节点和它的父亲节点。
void dfs(int u, int fno) {
// 初始化：第 2^0 = 1 个祖先就是它的父亲节点，dep 也比父亲节点多 1。
fa[u][0] = fno;
dep[u] = dep[fa[u][0]] + 1;
// 初始化：其他的祖先节点：第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第
// 2^(i-1) 的祖先节点。
for (int i = 1; i < LG; ++i) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
info[u][i] = info[fa[u][i - 1]][i - 1] + info[u][i - 1];
}
// 遍历子节点来进行 dfs。
for (int v : g[u]) {
if (v == fno)
continue;
dfs(v, u);
}
}
Info lca(int x, int y) {
// 令 y 比 x 深。
if (dep[x] > dep[y])
swap(x, y);
// 令 y 和 x 在一个深度。
Info a, b;
int tmp = dep[y] - dep[x];
for (int j = 0; tmp; ++j, tmp >>= 1)
if (tmp & 1)
b = info[y][j] + b, y = fa[y][j];
// 如果这个时候 y = x，那么 x，y 就都是它们自己的祖先。
if (y == x) {
return info[x][0] + b;
}
// 不然的话，找到第一个不是它们祖先的两个点。
for (int j = LG - 1; j >= 0 && y != x; --j) {
if (fa[x][j] != fa[y][j]) {
a = info[x][j] + a;
x = fa[x][j];
b = info[y][j] + b;
y = fa[y][j];
}
}
// 返回结果。
a = info[x][1] + a;
b = info[y][0] + b;
swap(a.max_prf, a.max_suf);
swap(a.min_prf, a.min_suf);
return a + b;
}
void add(int x, int y) {
g[x].push_back(y);
g[y].push_back(x);
}
void sol() {
int n;
cin >> n;
int cur = 2;
info[1][0] = Info(1);
vector<tuple<int, int, int>> q;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
if (s == "+") {
int v, val;
cin >> v >> val;
info[cur][0] = Info(val);
add(v, cur++);
} else {
int u, v, k;
cin >> u >> v >> k;
q.emplace_back(u, v, k);
}
}
dfs(1, 0);
for (auto [u, v, k] : q) {
auto rt = lca(u, v);
if (rt.min_seg <= k && k <= rt.max_seg) {
cout << "YES\\n";
} else {
cout << "NO\\n";
}
}
for (int i = 0; i < cur; i++) {
g[i].clear();
}
}
int main() {
cout << setprecision(15) << fixed;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef SINGLE_INPUT
int t;
cin >> t;
while (t--) {
sol();
}
#else
sol();
#endif
return 0;
}
dfs欧拉序，ST表
通过求出树的欧拉序，可以将树上最近公共祖先问题转化为区间问题。
求lca的rmq方法，先求树的欧拉序，并预处理出每个节点的深度。然后记录每个点x在欧拉序中的第一个位置p[x]。求两个点x和y的lca实际上就是欧拉序中的子区间[p[x], p[y]]中深度最小的点。
感觉单纯的求lca可以用，如果还有路径上的值需要维护，还得倍增。
//https://www.luogu.com.cn/problem/P3379
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;
vector<int> g[N];
vector<int> eulerTour;
int fc[N], dep[N];
void dfs(int u, int fno) {
dep[u] = dep[fno] + 1; // 每个节点的深度
// 每个节点欧拉序中第一次出现的位置
fc[u] = eulerTour.size(); // 每个节点第一次在欧拉序中出现的位置
eulerTour.push_back(u); // 欧拉序
for (auto v : g[u]) {
if (v == fno)
continue;
dfs(v, u);
eulerTour.push_back(u);
}
}
// 用st表维护欧拉序区间最小值，按照深度比较
struct ST {
vector<vector<int>> st; // st[i][j] 代表区间[i, i+2^j)最小值
ST(const vector<int>& a) : st(a.size(), vector<int>(30)) {
int sz = a.size();
for (int i = 0; i < sz; i++)
st[i][0] = a[i];
for (int j = 1; (1 << j) <= sz; j++) { // 区间大小
for (int i = 0; i + (1 << j) - 1 < sz; i++) { // 区间下限
int x = st[i][j - 1], y = st[i + (1 << (j - 1))][j - 1];
st[i][j] = dep[x] < dep[y] ? x : y;
}
}
}
int ask(int l, int r) {
int k = 0;
while ((1 << (k + 1)) <= r - l + 1)
k++;
int x = st[l][k], y = st[r - (1 << k) + 1][k];
return dep[x] < dep[y] ? x : y;
}
};
// 建图g
// 根为s则调用dfs(s,0)
// 通过欧拉序建立ST表
// 查找x和y的lca, st.ask(min(fc[x], fc[y]), max(fc[x], fc[y]))
void sol() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(s, 0);
ST st(eulerTour);
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
// 获取x和y的lca
cout << st.ask(min(fc[x], fc[y]), max(fc[x], fc[y])) << endl;
}
}
int main() {
cout << setprecision(15) << fixed;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef SINGLE_INPUT
int t;
cin >> t;
while (t--) {
sol();
}
#else
sol();
#endif
return 0;
}
离线，并查集
我们用vis数值记录每个节点是否被dfs遍历过。
深搜遍历子树u结束后（函数调用结束），子树的根节点在并查集上指向其父节点。
深搜遍历子树u在u的子节点全部遍历后（函数调用结束前），寻找查询中含u的点对(u,v)（这一步可以离线处理），若v已经被遍历vis[v] = true，则u和v的最近公共祖先就是并查集中v的根root。
// <https://www.luogu.com.cn/problem/P3379>
#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ull unsigned long long
#define ll long long
#define N 500005
#define MOD 998244353
using namespace std;
vector<int> g[N];
vector<pair<int, int>> q[N];
int vis[N], ans[N];
int fa[N];
int ufind(int x) {
return fa[x] < 0 ? x : fa[x] = ufind(fa[x]);
}
void tarjan(int u) {
vis[u] = 1;
for (auto v : g[u]) {
if (vis[v])
continue;
tarjan(v);
fa[v] = u;
}
for (auto [v, i] : q[u]) {
if (vis[v])
ans[i] = ufind(v);
}
}
void sol() {
int n, m, s;
cin >> n >> m >> s;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
q[x].emplace_back(y, i);
q[y].emplace_back(x, i);
}
memset(fa, -1, sizeof(fa));
tarjan(s);
for (int i = 0; i < m; i++) {
cout << ans[i] << "\\n";
}
}
int main() {
cout << setprecision(15) << fixed;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#ifndef SINGLE_INPUT
int t;
cin >> t;
while (t--) {
sol();
}
#else
sol();
#endif
return 0;
}