题目描述
给定
n
n
n 个节点的有根树，根节点为
1
1
1，每个节点上有权值
0
0
0 或
1
1
1；
共
q
q
q 次询问，每次询问
u
u
u 到
v
v
v 路径上的最大子段和。
数据范围
1
≤
n
≤
2
⋅
1
0
5
,
1
≤
q
≤
2
⋅
1
0
5
1 \leq n \leq 2 \cdot 10^5, 1 \leq q \leq 2 \cdot 10^5
1≤n≤2⋅105,1≤q≤2⋅105
题解报告
假设树的形状是一条链，即每次询问数组上一段连续区间内的最大子段和，
可以通过维护前缀和，计算询问区间内最大前缀和与最小前缀和，两者相减即为该询问区间的最大字段和。
对于树形结构，可以采用相同的思想，利用前缀和的差来计算答案。
考虑
u
u
u 是
v
v
v 的祖先（或反过来）的情况，
答案即为路径上最大前缀和最小前缀的差；
假如
u
u
u 和
v
v
v 之间不存在祖先关系，令
l
c
a
lca
lca 为两点的最近公共祖先，
则最大子段要么全部位于
l
c
a
lca
lca 到
u
u
u 的路径中，要么全部位于
l
c
a
lca
lca 到
v
v
v 的路径中，要么被
l
c
a
lca
lca 节点分成两部分；
对于前两种情况，和上述讨论是相同的；
对于第三种情况，答案即为
l
c
a
lca
lca 到
u
u
u 之间的最大前缀加上
l
c
a
lca
lca 到
v
v
v 之间的最大前缀减去
l
c
a
lca
lca 的前缀的两倍再加上
l
c
a
lca
lca 的权值。
归根到底都是求路径上的最大值和最小值，可以用树剖
+
+
+ 线段树维护；
不过有更简单的方法，倍增。
n
o
d
e
[
i
]
[
j
]
node[i][j]
node[i][j]，表示第
i
i
i 个节点向上
2
j
2^j
2j 步之间所有节点（不包括终点）的前缀和的最大值和最小值，
更新方式很传统，
n
o
d
e
[
i
]
[
j
]
=
m
a
x
/
m
i
n
(
n
o
d
e
[
i
]
[
j
−
1
]
,
n
o
d
e
[
f
a
[
i
]
[
j
−
1
]
]
[
j
−
1
]
)
node[i][j] = max/min (node[i][j - 1], node[fa[i][j - 1]][j - 1])
node[i][j]=max/min(node[i][j−1],node[fa[i][j−1]][j−1])。
AC代码：
#include <bits/stdc++.h>
#define ll long long
#define int ll
using namespace std;
const int N = 2e5 + 5;
const int M = 20;
struct Node {
int mx_suf, mx_seg;
int mn_suf, mn_seg;
void Merge (Node &a) {
this -> mx_seg = max ({this -> mx_seg, a.mx_seg, this -> mx_suf - a.mn_suf});
this -> mn_seg = min ({this -> mn_seg, a.mn_seg, this -> mn_suf - a.mx_suf});
this -> mx_suf = max (this -> mx_suf, a.mx_suf);
this -> mn_suf = min (this -> mn_suf, a.mn_suf);
}
};
int Get_lca (int u, int v, vector <vector <int> > &fa, vector <int> &dep) {
if (dep[u] < dep[v]) swap (u, v);
for (int i = M - 1; i >= 0; --i) {
if (dep[fa[u][i]] > dep[v]) u = fa[u][i];
}
if (dep[u] > dep[v]) u = fa[u][0];
for (int i = M - 1; i >= 0; --i) {
if (fa[u][i] != fa[v][i]) {
u = fa[u][i];
v = fa[v][i];
}
}
if (u != v) return fa[u][0];
else return u;
}
Node Get_ans (int u, int lca, vector <vector <Node> > &node,
vector <vector <int> > &fa, vector <int> &dep) {
Node ans = {-1, -1, -1, -1};
for (int i = M - 1; i >= 0; --i) {
if (dep[fa[u][i]] >= dep[lca]) {
if (ans.mx_seg == -1) ans = node[u][i];
else ans.Merge (node[u][i]);
u = fa[u][i];
}
}
if (ans.mx_seg == -1) ans = node[u][0];
else ans.Merge (node[u][0]);
return ans;
}
int t, n;
void init () {}
void charming () {
init ();
cin >> n;
vector <vector <int> > fa (n + 5, vector <int> (M));
vector <vector <Node> > node (n + 5, vector <Node> (M));
node[1][0] = (Node) {1, 1, 1, 0};
vector <int> suf (n + 5), dep (n + 5), val (n + 5);
suf[1] = dep[1] = val[1] = 1;
for (int i = 1; i < M; ++i) node[1][i] = node[1][i - 1];
char op;
for (int i = 1, u, v, x, k, cnt = 1, mn, mx, lca; i <= n; ++i) {
cin >> op;
if (op == '+') {
++cnt, cin >> v >> x;
fa[cnt][0] = v;
for (int i = 1; i < M; ++i) fa[cnt][i] = fa[fa[cnt][i - 1]][i - 1];
suf[cnt] = suf[v] + x, dep[cnt] = dep[v] + 1, val[cnt] = x;
node[cnt][0] = (Node) {suf[cnt], max (0ll, x), suf[cnt], min (0ll, x)};
for (int i = 1; i < M; ++i) {
node[cnt][i] = node[cnt][i - 1];
node[cnt][i].Merge (node[fa[cnt][i - 1]][i - 1]);
}
} else {
cin >> u >> v >> k;
mn = mx = 0;
lca = Get_lca (u, v, fa, dep);
Node ans_u = Get_ans (u, lca, node, fa, dep);
Node ans_v = Get_ans (v, lca, node, fa, dep);
mn = min ({mn, ans_u.mn_seg, ans_v.mn_seg, ans_u.mn_suf + ans_v.mn_suf - suf[lca] * 2 + val[lca]});
mx = max ({mx, ans_u.mx_seg, ans_v.mx_seg, ans_u.mx_suf + ans_v.mx_suf - suf[lca] * 2 + val[lca]});
if (k >= mn && k <= mx) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
}
signed main () {
cin >> t;
while (t--) charming ();
return 0;
}
后记
想了半天都没想出来怎么写的，看了别人的代码才发现这么简单…主要是刚开始方向都没对，到后面都想到了线段树合并那里了。
