# 某岛

… : "…アッカリ～ン . .. . " .. .
January 18, 2023

# dfs 序求 lca

## 前情提要

…but wait, 你的 lca 在哪里。。。

まさか？…

## LCA

dfs 序也可以求 lca？

### Luogu. P3379 【模板】最近公共祖先（LCA）

```#include &lt;lastweapon/bitwise&gt;
using namespace lastweapon;
const int N = int(5e5) + 9, LV = 20;
int fa[LV][N], dep[N];

int move_up(int x, int d) {
for (int lv=0;d;++lv,d&gt;&gt;=1)
if (d&amp;1) x = fa[lv][x];
return x;
}

inline int lca(int x, int y) {
if (dep[y] &lt; 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(&quot;in.txt&quot;, &quot;r&quot;, stdin);
#endif

<pre><code>int m, s; RD(n, m, s);

DO(n-1) {
int x, y; RD(x, y);
}

dfs(s);

DO(m) {
int a, b; RD(a, b);
printf(&amp;quot;%d\n&amp;quot;, lca(a, b));
}
</code></pre>

}

```
```#include &lt;lastweapon/bitwise&gt;
using namespace lastweapon;
const int N = int(5e5) + 9, LM = 19;
int dfn[N], ST[LM][N], dep[N], nn;

inline bool cmp(int a, int b) {
return dep[a] &lt; dep[b];
}
inline int lca(int a, int b) {
if (a == b) return a;
int l = dfn[a], r = dfn[b];
if (l &gt; r) swap(l, r); int lv = lg2(r-l++);
return min(ST[lv][l], ST[lv][r-(1&lt;&lt;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) &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);
}
}
}

int main() {

#ifndef ONLINE_JUDGE
freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);
//freopen(&quot;/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt&quot;, &quot;w&quot;, stdout);
#endif

<pre><code>int m, s; RD(n, m, s);

DO(n-1) {
int x, y; RD(x, y);
}

dfs(s); init_rmq();

DO(m) {
int a, b; RD(a, b);
printf(&amp;quot;%d\n&amp;quot;, lca(a, b));
}
</code></pre>

}
```
```#include &lt;lastweapon/bitwise&gt;
const int N = int(5e5) + 9;
int A[N], T[4*N];
int dfn[N], dep[N], nn;

#define lx (x&lt;&lt;1)
#define rx (lx|1)
#define ml ((l+r)&gt;&gt;1)
#define mr (ml+1)
#define lc lx,l,ml
#define rc rx,mr,r

bool cmp(int a, int b) {
return dep[a] &lt; 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 &lt; l || r &lt; a) return 0;
if (a &lt;= l &amp;&amp; r &lt;= 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 &gt; 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(&quot;in.txt&quot;, &quot;r&quot;, stdin);
//freopen(&quot;/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt&quot;, &quot;w&quot;, stdout);
#endif

<pre><code>dep[0] = INF;

int m, s; RD(n, m, s);

DO(n-1) {
int x, y; RD(x, y);
}

dfs(s); Build(1, 1, n);

DO(m) {
int a, b; RD(a, b);
printf(&amp;quot;%d\n&amp;quot;, lca(a, b));
}
</code></pre>

}
```

### BZOJ 2819. Nim

• https://darkbzoj.cc/problem/2819
。。。首先这个题还必须得用我们新学会的招式。。因为 euler 序恰好被卡内存。。。（怪不得大家都只写倍增和树剖。。）
```#include &lt;lastweapon/bitwise&gt;
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&lt;=n;x+=low_bit(x)) C[x] ^= w;
}
} using namespace BIT;

inline bool elder(int a, int b) {
return dep[a] &lt; dep[b];
}

inline int lca(int a, int b) {
if (a == b) return a;
int l = L[a], r = L[b];
if (l &gt; r) swap(l, r); int lv = lg2(r-l++);
return min(ST[lv][l], ST[lv][r-(1&lt;&lt;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(&quot;in.txt&quot;, &quot;r&quot;, stdin);
//freopen(&quot;/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt&quot;, &quot;w&quot;, stdout);
#endif

<pre><code>RD(n); REP_1(i, n) RD(W[i]); DO(n-1) {
int a, b; RD(a, b);
}

dfs();

for ( int lv = 1 ; _1(lv) &amp;lt;= nn ; lv ++ ){
for ( int i = 1 ; i + _1(lv)  &amp;lt;= nn + 1 ; i ++ )
ST[lv][i] = min(ST[lv-1][i], ST[lv-1][i + _1(lv-1)], elder);
}

Rush {
if (RC() == &amp;#039;Q&amp;#039;) {
int a, b; RD(a, b);
puts(Sum(L[a])^Sum(L[b])^W[lca(a, b)] ? &amp;quot;Yes&amp;quot; : &amp;quot;No&amp;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 &lt;lastweapon/bitwise&gt;
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];

inline bool cmp_by_dep(int a, int b) {
return dep[a] &lt; dep[b];
}
inline bool cmp_by_dfn(int a, int b) {
return dfn[a] &lt; dfn[b];
}
inline int lca(int a, int b) {
if (a == b) return a;
int l = dfn[a], r = dfn[b];
if (l &gt; r) swap(l, r); int lv = lg2(r-l++);
return min(ST[lv][l], ST[lv][r-(1&lt;&lt;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&lt;&lt;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&lt;&lt;lv)+1], cmp_by_dfn);
}

void dfs(int u = 1, int p = 0) {
ST[0][dfn[u] = ++nn] = p;
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) &amp;lt;= nn ; lv ++ ) {
for ( int i = 1 ; i + _1(lv)  &amp;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(&quot;in.txt&quot;, &quot;r&quot;, stdin);
//freopen(&quot;/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt&quot;, &quot;w&quot;, stdout);
#endif

<pre><code>int q; RD(n, q); FOR_1(i, 2, n) {
}

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(&amp;quot;%d %d\n&amp;quot;, z.se, z.fi);
}
</code></pre>

}

```

## 直径

### SPOJ PT07Z. Longest path in a tree

```#include &lt;lastweapon/bitwise&gt;
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 &lt; m &lt;= r
// d 深度
// dd 父亲的深度

#define lx (x&lt;&lt;1)
#define rx (lx|1)
#define ml ((l+r)&gt;&gt;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;
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(&quot;in.txt&quot;, &quot;r&quot;, stdin);
//freopen(&quot;/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt&quot;, &quot;w&quot;, 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;
}

dfs(); Build(1, 1, n);
cout &amp;lt;&amp;lt; T[1].D &amp;lt;&amp;lt; endl;
</code></pre>

}

```

### CEOI 2019 day 1 B. Dynamic Diameter

• https://codeforces.com/contest/1192/submission/189685098
终于要进入正篇了。。果然还是需要动态直径方能体现这个做法的强大之处。。。
只要在上面的代码稍稍修改，支持两种修改操作，
一种区间修改，修改子树里所有的 d 值 和 dd 值。。
一种单点修改，因为上面修改 u 所在的子树的时候，u 结点自己的 dd 其实是不被影响的，要修正回来。

```#include &lt;lastweapon/bitwise&gt;
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;
}
d += a; dd += a*2;
ld -= a; rd -= a;
d0 += a;
}
} T[N*4];

// l &lt; m &lt;= r
// max d[l] + d[r] - dd[m]
// d 深度
// dd 父亲的深度

#define lx (x&lt;&lt;1)
#define rx (lx|1)
#define ml ((l+r)&gt;&gt;1)
#define mr (ml+1)
#define lc lx,l,ml
#define rc rx,mr,r

void rls(int x) {
if (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 &lt; l || r &lt; a) return;
if (a &lt;= l &amp;&amp; r &lt;= b) {
} 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 &lt; 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;
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(&quot;in.txt&quot;, &quot;r&quot;, stdin);
//freopen(&quot;/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt&quot;, &quot;w&quot;, 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]);
}

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(&amp;quot;%lld\n&amp;quot;, last_ans = T[1].D);
}
</code></pre>

}
```

### 2019 ICPC 上海赛区网络赛 Problem A. Lightning Routing I

```#include &lt;lastweapon/bitwise&gt;
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&lt;LL, int&gt; d, ld, rd;
pair&lt;LL, PII&gt; 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};
}
d.fi += a; dd += a*2;
ld.fi -= a; rd.fi -= a;
d0 += a;
}
} T[N*4];

// l &lt; m &lt;= r
// max d[l] + d[r] - dd[m]
// d 深度
// dd 父亲的深度

#define lx (x&lt;&lt;1)
#define rx (lx|1)
#define ml ((l+r)&gt;&gt;1)
#define mr (ml+1)
#define lc lx,l,ml
#define rc rx,mr,r
void rls(int x) {
if (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 &lt; l || r &lt; a) return INFF;
if (a &lt;= l &amp;&amp; r &lt;= 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 &lt; 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 &lt; l || r &lt; a) return;
if (a &lt;= l &amp;&amp; r &lt;= b) {
} 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 &lt; 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;
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 &gt; 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(&quot;in.txt&quot;, &quot;r&quot;, stdin);
//freopen(&quot;/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt&quot;, &quot;w&quot;, stdout);
#endif

<pre><code>dep[0] = INFF;

RD(n); REP_1(i, n-1) {
int x, y; RD(x, y, W[i]);
}

dfs(); Build(1, 1, n);

Rush {
if (RC() == &amp;#039;Q&amp;#039;) {
int x; RD(x);
auto D = T[1].D;
int a = D.se.fi, b = D.se.se;
printf(&amp;quot;%lld\n&amp;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>

}
```