前情提要
前几天做了一下 Educational Codeforces Round 141 的 F 题。。。看起来是个动态直径，之前网赛我出过一次，翻出标程应该能秒。但是写起来发现要改的地方实在很多，大概是我的标程实在不怎么高明。
于是看了一下代码最短的家伙们都写了啥，于是我被 这份代码 震惊了。
第一反应是，虽然转移我看不懂，但是应该就是一颗 zkw 树，等价于 这篇文章里所提到的算法三 嘛。。。
…but wait, 你的 lca 在哪里。。。
之前 Dynamic Diameter 里我们是在 euler 序上建线段树。。。实际上是隐含了一个求 lca 的过程的。。。
但是这里明显是 dfs 序吧。。。。。。
まさか？…
Table of Contents
LCA
dfs 序也可以求 lca？
搜了一下，原来还真有！
核心思想：虽然 lca 自己不会出现在区间里。。但是你的孩子会啊。。。找到这个点再求父亲，或者，直接在建 st 表的时候就直接放父结点就行了！
好吧。。反正我是想不到。。囧。。
这个板子显然各方面都是完胜 euler 序 lca 的。。。特别是有的题里同时出现 dfs 序和 lca 的时候 —— 妈妈再也不用担心搞不清时间戳哪个对哪个了。。。
找点例题练习一下吧。。
Luogu. P3379 【模板】最近公共祖先（LCA）
#include <lastweapon/bitwise>
using namespace lastweapon;
const int N = int(5e5) + 9, LV = 20;
int fa[LV][N], dep[N];
VI adj[N]; int n;
int move_up(int x, int d) {
for (int lv=0;d;++lv,d>>=1)
if (d&1) x = fa[lv][x];
return x;
}
inline int lca(int x, int y) {
if (dep[y] < dep[x]) swap(x, y); y = move_up(y, dep[y] - dep[x]); if (x == y) return x;
DWN(lv, LV, 0) if (fa[lv][x] != fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
return fa[0][x];
}
void dfs(int u = 1, int p = 0) {
for (auto v: adj[u]) if (v != p) {
dep[v] = dep[u] + 1;
fa[0][v] = u; for (int lv=0;fa[lv+1][v]=fa[lv][fa[lv][v]];++lv);
dfs(v, u);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
<pre><code>int m, s; RD(n, m, s);
DO(n-1) {
int x, y; RD(x, y);
adj[x].PB(y);
adj[y].PB(x);
}
dfs(s);
DO(m) {
int a, b; RD(a, b);
printf(&quot;%d\n&quot;, lca(a, b));
}
</code></pre>
}
#include <lastweapon/bitwise>
using namespace lastweapon;
const int N = int(5e5) + 9, LM = 19;
int dfn[N], ST[LM][N], dep[N], nn;
VI adj[N]; int n;
inline bool cmp(int a, int b) {
return dep[a] < dep[b];
}
inline int lca(int a, int b) {
if (a == b) return a;
int l = dfn[a], r = dfn[b];
if (l > r) swap(l, r); int lv = lg2(r-l++);
return min(ST[lv][l], ST[lv][r-(1<<lv)+1], cmp);
}
void dfs(int u = 1, int p = 0) {
ST[0][dfn[u] = ++nn] = p;
for (auto v: adj[u]) if (v != p) {
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
void init_rmq() {
for ( int lv = 1 ; _1(lv) <= nn ; lv ++ ) {
for ( int i = 1 ; i + _1(lv) <= nn + 1 ; i ++ ) {
ST[lv][i] = min(ST[lv-1][i], ST[lv-1][i + _1(lv-1)], cmp);
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
<pre><code>int m, s; RD(n, m, s);
DO(n-1) {
int x, y; RD(x, y);
adj[x].PB(y);
adj[y].PB(x);
}
dfs(s); init_rmq();
DO(m) {
int a, b; RD(a, b);
printf(&quot;%d\n&quot;, lca(a, b));
}
</code></pre>
}
#include <lastweapon/bitwise>
const int N = int(5e5) + 9;
int A[N], T[4*N];
int dfn[N], dep[N], nn;
VI adj[N]; int n;
#define lx (x<<1)
#define rx (lx|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx,l,ml
#define rc rx,mr,r
bool cmp(int a, int b) {
return dep[a] < dep[b];
}
void upd(int x) {
T[x] = min(T[lx], T[rx], cmp);
}
void Build(int x, int l, int r) {
if (l == r) {
T[x] = A[l];
} else {
Build(lc);
Build(rc);
upd(x);
}
}
int Query(int x, int l, int r, const int a, const int b) {
if (b < l || r < a) return 0;
if (a <= l && r <= b) {
return T[x];
} else {
return min(Query(lc, a, b), Query(rc, a, b), cmp);
}
}
int lca(int a, int b) {
if (a == b) return a;
a = dfn[a]; b = dfn[b]; if (a > b) swap(a, b); ++a;
return Query(1, 1, n, a, b);
}
void dfs(int u = 1, int p = 0) {
A[dfn[u] = ++nn] = p;
for (auto v: adj[u]) if (v != p) {
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
<pre><code>dep[0] = INF;
int m, s; RD(n, m, s);
DO(n-1) {
int x, y; RD(x, y);
adj[x].PB(y);
adj[y].PB(x);
}
dfs(s); Build(1, 1, n);
DO(m) {
int a, b; RD(a, b);
printf(&quot;%d\n&quot;, lca(a, b));
}
</code></pre>
}
BZOJ 2819. Nim
- https://darkbzoj.cc/problem/2819
。。。首先这个题还必须得用我们新学会的招式。。因为 euler 序恰好被卡内存。。。（怪不得大家都只写倍增和树剖。。）
#include <lastweapon/bitwise>
using namespace lastweapon;
const int N = int(5e5) + 9, LM = 19;
int W[N], L[N], R[N], ST[LM][N], dep[N], nn;
VI adj[N]; int n; int fa[N];
namespace BIT{
int C[N];
int Sum(int x){
int z=0; for (;x;x^=low_bit(x)) z ^= C[x];
return z;
}
void Xor(int x, int w){
for(;x<=n;x+=low_bit(x)) C[x] ^= w;
}
} using namespace BIT;
inline bool elder(int a, int b) {
return dep[a] < dep[b];
}
inline int lca(int a, int b) {
if (a == b) return a;
int l = L[a], r = L[b];
if (l > r) swap(l, r); int lv = lg2(r-l++);
return min(ST[lv][l], ST[lv][r-(1<<lv)+1], elder);
}
void upd(int u, int w) {
Xor(L[u], w);
Xor(R[u]+1, w);
}
void dfs(int u = 1, int p = -1) {
ST[0][L[u] = ++nn] = p;
for (auto v: adj[u]) if (v != p) {
dep[v] = dep[u] + 1;
dfs(v, u);
}
R[u] = nn;
upd(u, W[u]);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
<pre><code>RD(n); REP_1(i, n) RD(W[i]); DO(n-1) {
int a, b; RD(a, b);
adj[a].PB(b);
adj[b].PB(a);
}
dfs();
for ( int lv = 1 ; _1(lv) &lt;= nn ; lv ++ ){
for ( int i = 1 ; i + _1(lv) &lt;= nn + 1 ; i ++ )
ST[lv][i] = min(ST[lv-1][i], ST[lv-1][i + _1(lv-1)], elder);
}
Rush {
if (RC() == &#039;Q&#039;) {
int a, b; RD(a, b);
puts(Sum(L[a])^Sum(L[b])^W[lca(a, b)] ? &quot;Yes&quot; : &quot;No&quot;);
} else {
int u, w; RD(u, w);
upd(u, W[u]^w);
W[u] = w;
}
}
</code></pre>
}
Codeforces Round #520, Problem E. Company
- https://codeforces.com/contest/1062/problem/E
一堆结点的 lca 是 dfs 序里最左和最右两个结点的 lca（这个结论建虚树的时候会用）。
因而还需要对以结点为下标，以cmp_by_dfn为比较函数，再分别建两组 st 表，加上 lca 自己的 st 表一共有 3 组。
询问的时候讨论一下删左还是删右即可。
#include <lastweapon/bitwise>
using namespace lastweapon;
const int N = int(1e5) + 9, LM = 19;
int dfn[N], ST[LM][N], dep[N], nn;
int st[LM][N], ts[LM][N];
VI adj[N]; int n;
inline bool cmp_by_dep(int a, int b) {
return dep[a] < dep[b];
}
inline bool cmp_by_dfn(int a, int b) {
return dfn[a] < dfn[b];
}
inline int lca(int a, int b) {
if (a == b) return a;
int l = dfn[a], r = dfn[b];
if (l > r) swap(l, r); int lv = lg2(r-l++);
return min(ST[lv][l], ST[lv][r-(1<<lv)+1], cmp_by_dep);
}
inline int mn(int l, int r) {
int lv = lg2(r-l+1);
return min(st[lv][l], st[lv][r-(1<<lv)+1], cmp_by_dfn);
}
inline int mx(int l, int r) {
int lv = lg2(r-l+1);
return max(ts[lv][l], ts[lv][r-(1<<lv)+1], cmp_by_dfn);
}
void dfs(int u = 1, int p = 0) {
ST[0][dfn[u] = ++nn] = p;
for (auto v: adj[u]) {
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
void init_rmq() {
REP_1(i, n) st[0][i] = ts[0][i] = i;
<pre><code>for ( int lv = 1 ; _1(lv) &lt;= nn ; lv ++ ) {
for ( int i = 1 ; i + _1(lv) &lt;= nn + 1 ; i ++ ) {
ST[lv][i] = min(ST[lv-1][i], ST[lv-1][i + _1(lv-1)], cmp_by_dep);
st[lv][i] = min(st[lv-1][i], st[lv-1][i + _1(lv-1)], cmp_by_dfn);
ts[lv][i] = max(ts[lv-1][i], ts[lv-1][i + _1(lv-1)], cmp_by_dfn);
}
}
</code></pre>
}
PII f(int l, int r, int x) {
int a, b;
if (x == l) {
a = mn(x+1, r); b = mx(x+1, r);
} else if (x == r) {
a = mn(l, x-1); b = mx(l, x-1);
} else {
a = min(mn(l, x-1), mn(x+1, r), cmp_by_dfn);
b = max(mx(l, x-1), mx(x+1, r), cmp_by_dfn);
}
return {dep[lca(a, b)], x};
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
<pre><code>int q; RD(n, q); FOR_1(i, 2, n) {
adj[RD()].PB(i);
}
dfs(); init_rmq();
DO(q) {
int l, r; RD(l, r);
int a = mn(l, r), b = mx(l, r);
PII z = max(f(l, r, a), f(l, r, b));
printf(&quot;%d %d\n&quot;, z.se, z.fi);
}
</code></pre>
}
直径
SPOJ PT07Z. Longest path in a tree
树的直径是一个非常经典的问题，做法极多。比如 dfs() 两次，树形 dp，都非常经典。
其中基于线段树区间合并，维护直径也是一个大家熟知的算法 —— 因为任意两个连通块合并后的直径，一定端点还在原先的两组端点上。
这个方法不仅能求全局直径，还能求子树直径，删掉一些子树后的连通块的直径，甚至虚树直径什么的。。。
缺点是转移时要各种讨论。
这里我们从上面提到的 dfs 求 lca 的思路出发，可将一段子树的直径转换为 max d[l]+d[r]-2dd[m] | l < m <= r。
虽然代码里没有 lca，但是其实本质处处都是 lca —— 上述公式里的 m 就隐含了求 lca 的过程。
#include <lastweapon/bitwise>
using namespace lastweapon;
const int N = int(1e5) + 9;
int L[N], R[N], dep[N], fa[N], id[N], nn;
VII adj[N]; LL W[N]; int n;
struct rec{
LL d, dd, ld, rd, D;
void init(LL _d, LL _dd) {
d = _d; dd = 2*_dd;
D = ld = -INFF; rd = _d - dd;
}
} T[N*4];
// max d[l] + d[r] - dd[m]
// l < m <= r
// d 深度
// dd 父亲的深度
#define lx (x<<1)
#define rx (lx|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx,l,ml
#define rc rx,mr,r
void upd(int x) {
T[x].d = max(T[lx].d, T[rx].d);
T[x].dd = min(T[lx].dd, T[rx].dd);
T[x].ld = max(T[lx].ld, T[rx].ld, T[lx].d - T[rx].dd);
T[x].rd = max(T[lx].rd, T[rx].rd, T[rx].d - T[lx].dd);
T[x].D = max(T[lx].D, T[rx].D, T[lx].ld + T[rx].d, T[lx].d + T[rx].rd);
}
void Build(int x, int l, int r) {
if (l == r) {
T[x].init(dep[id[l]], dep[fa[id[l]]]);
} else {
Build(lc);
Build(rc);
upd(x);
}
}
void dfs(int u = 1, int p = 0) {
id[L[u] = ++nn] = u;
for (auto it: adj[u]) {
int v = it.fi; if (v == p) continue;
dep[v] = dep[u] + W[it.se]; fa[v] = u;
dfs(v, u);
}
R[u] = nn;
}
int main() {
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
<pre><code>dep[0] = INF;
int q; LL w; RD(n);
REP_1(i, n-1) {
int x, y; RD(x, y); W[i] = 1;
adj[x].PB({y,i});
adj[y].PB({x,i});
}
dfs(); Build(1, 1, n);
cout &lt;&lt; T[1].D &lt;&lt; endl;
</code></pre>
}
CEOI 2019 day 1 B. Dynamic Diameter
- https://codeforces.com/contest/1192/submission/189685098
终于要进入正篇了。。果然还是需要动态直径方能体现这个做法的强大之处。。。
只要在上面的代码稍稍修改，支持两种修改操作，
一种区间修改，修改子树里所有的 d 值 和 dd 值。。
一种单点修改，因为上面修改 u 所在的子树的时候，u 结点自己的 dd 其实是不被影响的，要修正回来。
而这些都是线段树的常规操作了。。。
#include <lastweapon/bitwise>
using namespace lastweapon;
const int N = int(1e5) + 9;
int L[N], R[N], fa[N], id[N], EtoV[N], nn;
VII adj[N]; LL dep[N], W[N]; int n;
struct rec{
LL d, dd, ld, rd, D, d0;
void init(LL _d, LL _dd) {
d = _d; dd = _dd*2;
D = ld = -INFF; rd = _d - dd;
}
void add(LL a) {
d += a; dd += a*2;
ld -= a; rd -= a;
d0 += a;
}
} T[N*4];
// l < m <= r
// max d[l] + d[r] - dd[m]
// d 深度
// dd 父亲的深度
#define lx (x<<1)
#define rx (lx|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx,l,ml
#define rc rx,mr,r
void rls(int x) {
if (T[x].d0) {
T[lx].add(T[x].d0);
T[rx].add(T[x].d0);
T[x].d0 = 0;
}
}
void upd(int x) {
T[x].d = max(T[lx].d, T[rx].d);
T[x].dd = min(T[lx].dd, T[rx].dd);
T[x].ld = max(T[lx].ld, T[rx].ld, T[lx].d - T[rx].dd);
T[x].rd = max(T[lx].rd, T[rx].rd, T[rx].d - T[lx].dd);
T[x].D = max(T[lx].D, T[rx].D, T[lx].ld + T[rx].d, T[lx].d + T[rx].rd);
}
void Build(int x, int l, int r) {
if (l == r) {
T[x].init(dep[id[l]], dep[fa[id[l]]]);
} else {
Build(lc);
Build(rc);
upd(x);
}
}
void Modify(int x, int l, int r, int a, int b, LL d) {
if (b < l || r < a) return;
if (a <= l && r <= b) {
T[x].add(d);
} else {
rls(x);
Modify(lc, a, b, d);
Modify(rc, a, b, d);
upd(x);
}
}
void Modify(int x, int l, int r, int p, LL d) {
if (l == r) {
T[x].init(T[x].d, T[x].dd/2 + d);
} else {
rls(x);
if (p < mr) Modify(lc, p, d);
else Modify(rc, p, d);
upd(x);
}
}
void dfs(int u = 1, int p = 0) {
id[L[u] = ++nn] = u;
for (auto it: adj[u]) {
int v = it.fi; if (v == p) continue;
dep[v] = dep[u] + W[it.se]; fa[v] = u; EtoV[it.se] = v;
dfs(v, u);
}
R[u] = nn;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
<pre><code>dep[0] = INFF;
int q; LL w; RD(n, q, w);
REP(i, n-1) {
int x, y; RD(x, y, W[i]);
adj[x].PB({y,i});
adj[y].PB({x,i});
}
dfs(); Build(1, 1, n);
DO(q) {
int t; LL v; RD(t, v);
t = (t + last_ans) % (n-1);
v = (v + last_ans) % w;
LL d = v - W[t]; int x = EtoV[t];
Modify(1, 1, n, L[x], R[x], d);
Modify(1, 1, n, L[x], -d);
W[t] = v;
printf(&quot;%lld\n&quot;, last_ans = T[1].D);
}
</code></pre>
}
2019 ICPC 上海赛区网络赛 Problem A. Lightning Routing I
再来看这题，在上题的基础上，还需要维护直径的端点。
设直径为 (a, b)，那么答案就是 max(dist(x, a), dist(x, b))。
这里的 dist 正常也是需要求 lca 的，但是现在我们发现要减去的那玩意儿已经包含在我们线段树之中了。。。
直接 query 出来即可。
#include <lastweapon/bitwise>
using namespace lastweapon;
const int N = int(1e5) + 9;
int W[N], L[N], R[N], fa[N], id[N], EtoV[N], nn;
VII adj[N]; LL dep[N]; int n;
struct rec{
pair<LL, int> d, ld, rd;
pair<LL, PII> D; LL dd, d0;
void init(LL _d, LL _dd, int x) {
d = {_d, x}; dd = _dd*2;
D = {-INFF, {0,0}};
ld = {-INFF, 0};
rd = {_d - dd, x};
}
void add(LL a) {
d.fi += a; dd += a*2;
ld.fi -= a; rd.fi -= a;
d0 += a;
}
} T[N*4];
// l < m <= r
// max d[l] + d[r] - dd[m]
// d 深度
// dd 父亲的深度
#define lx (x<<1)
#define rx (lx|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx,l,ml
#define rc rx,mr,r
void rls(int x) {
if (T[x].d0) {
T[lx].add(T[x].d0);
T[rx].add(T[x].d0);
T[x].d0 = 0;
}
}
void upd(int x) {
T[x].d = max(T[lx].d, T[rx].d);
T[x].dd = min(T[lx].dd, T[rx].dd);
T[x].ld = max(T[lx].ld, T[rx].ld, {T[lx].d.fi - T[rx].dd, T[lx].d.se});
T[x].rd = max(T[lx].rd, T[rx].rd, {T[rx].d.fi - T[lx].dd, T[rx].d.se});
T[x].D = max(T[lx].D, T[rx].D,{T[lx].ld.fi + T[rx].d.fi, {T[lx].ld.se, T[rx].d.se}},{T[lx].d.fi + T[rx].rd.fi, {T[lx].d.se, T[rx].rd.se}});
}
void Build(int x, int l, int r) {
if (l == r) {
T[x].init(dep[id[l]], dep[fa[id[l]]], id[l]);
} else {
Build(lc);
Build(rc);
upd(x);
}
}
LL Query(int x, int l, int r, const int a, const int b) {
if (b < l || r < a) return INFF;
if (a <= l && r <= b) {
return T[x].dd;
} else {
rls(x);
return min(Query(lc, a, b), Query(rc, a, b));
}
}
LL Query(int x, int l, int r, const int p) {
if (l == r) {
return T[x].d.fi;
} else {
rls(x);
return p < mr ? Query(lc, p) : Query(rc, p);
}
}
void Modify(int x, int l, int r, const int a, const int b, const LL d) {
if (b < l || r < a) return;
if (a <= l && r <= b) {
T[x].add(d);
} else {
rls(x);
Modify(lc, a, b, d);
Modify(rc, a, b, d);
upd(x);
}
}
void Modify(int x, int l, int r, const int p, const LL d) {
if (l == r) {
T[x].init(T[x].d.fi, T[x].dd/2 + d, id[l]);
} else {
rls(x);
if (p < mr) Modify(lc, p, d);
else Modify(rc, p, d);
upd(x);
}
}
void dfs(int u = 1, int p = 0) {
id[L[u] = ++nn] = u;
for (auto it: adj[u]) {
int v = it.fi; if (v == p) continue;
dep[v] = dep[u] + W[it.se]; fa[v] = u; EtoV[it.se] = v;
dfs(v, u);
}
R[u] = nn;
}
LL dist(int x, int y) {
if (x == y) return 0;
x = L[x], y = L[y]; if (x > y) swap(x, y);
return Query(1,1,n,x) + Query(1,1,n,y) - Query(1,1,n,x+1,y);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
<pre><code>dep[0] = INFF;
RD(n); REP_1(i, n-1) {
int x, y; RD(x, y, W[i]);
adj[x].PB({y,i});
adj[y].PB({x,i});
}
dfs(); Build(1, 1, n);
Rush {
if (RC() == &#039;Q&#039;) {
int x; RD(x);
auto D = T[1].D;
int a = D.se.fi, b = D.se.se;
printf(&quot;%lld\n&quot;, max(dist(x, a), dist(x, b)));
} else {
int i, w; RD(i, w);
LL d = w - W[i]; int x = EtoV[i];
Modify(1, 1, n, L[x], R[x], d);
Modify(1, 1, n, L[x], -d);
W[i] = w;
}
}
</code></pre>
}
Educational Codeforces Round 141, Problem G. Weighed Tree Radius
终于又回到了最初的起点… 现在再理解血小板神的代码就应该要简单多了吧。
因为这题里的修改的只涉及点权，而点权不会影响子树状态，所以只需要单点修改，zkw 树就可以了。
又因为这里只有单位权，所以其实可以 dd 也可以不用取 lca 的深度 —— 反正和 lca 就差 1。
这样代码可以更加简洁。
