# 20220320-DFS 序&欧拉序列¶

< 0.5h 时间戳 祖孙询问(LOJ10135) 提高 https://loj.ac/p/10135
< 0.75h 时间戳 AtCoder abc202 E Count Descendants 提高+ https://atcoder.jp/contests/abc202/tasks/abc202_e
<1h 欧拉序列 USACO 2019 Feb G. Cow Land 提高+ https://www.luogu.com.cn/problem/P6098
<2h 欧拉序列 USACO 2019 Dec G. Milk Visits(离线算法) 提高+ https://www.luogu.com.cn/problem/P5838

<1h 欧拉序列 USACO 2019 Dec G. Milk Visits(禁止离线算法) NOI- https://www.luogu.com.cn/problem/P5838
<1h 时间戳 [SDOI2015]寻宝游戏 NOI- https://www.luogu.com.cn/problem/P3320
<1h 时间戳 USACO 2019 Dec P. Bessie's Snow Cow NOI- https://www.luogu.com.cn/problem/P5852
<2h 欧拉序列 IOI2009 – Regions NOI https://www.luogu.com.cn/problem/P5901
<1.5h 时间戳 CF838B Diverging Directions NOI- https://codeforces.com/contest/838/problem/B

## Milking Visits¶

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
const int NN = 1e5 + 4;
int T[NN];
struct LCA {
static const int HH = 18;
int timer = 0, Tin[NN], fa[HH][NN], Dep[NN];
vi G[NN], W[NN];
vector<pair<int, int>> X[NN];
void addEdge(int u, int v) { G[u].push_back(v), G[v].push_back(u); }
void dfs(int u, int f) {
auto &w = W[T[u]];
auto &x = X[T[u]];
w.push_back(u), x.push_back({Tin[u] = timer++, u});
fa[0][u] = f, Dep[u] = Dep[f] + 1;
for (int k = 1; k < HH; ++k) fa[k][u] = fa[k - 1][fa[k - 1][u]];
for (int v : G[u])
if (v != f) dfs(v, u);
w.pop_back(), x.push_back({timer, !w.empty() ? w.back() : 0});
}
int lca(int u, int v) {
if (Dep[u] < Dep[v]) swap(u, v);
for (int k = HH - 1; k >= 0; --k)
if ((Dep[u] - Dep[v]) & (1 << k)) u = fa[k][u];
for (int k = HH - 1; k >= 0; --k)
if (fa[k][u] != fa[k][v]) u = fa[k][u], v = fa[k][v];
return u == v ? u : fa[0][u];
}
int last(int u, int c) {
auto &x = X[c];
auto it = upper_bound(begin(x), end(x), make_pair(Tin[u], NN + 10));
return it == begin(x) ? 0 : prev(it)->second;
}
} L;
int solve(int u, int v, int c) {
int d = L.lca(u, v), a = L.last(u, c);
if (a && L.Dep[a] >= L.Dep[d]) return 1;
a = L.last(v, c);
return a && L.Dep[a] >= L.Dep[d];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, M;
cin >> N >> M;
for (int i = 1; i <= N; ++i) cin >> T[i];
for (int i = 1, u, v; i < N; ++i) cin >> u >> v, L.addEdge(u, v);
L.dfs(1, 0);
for (int i = 0, A, B, C; i < M; ++i)
cin >> A >> B >> C, cout << solve(A, B, C);
cout << endl;
}

## 寻宝游戏¶

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int NN = 1e5 + 4;
struct Edge {
int v, w;
};
LL Dis[NN];
int N, L, M, UP[NN][18], Tin[NN], Tout[NN], Timer;
vector<Edge> G[NN];
void dfs(int u, int fa) {
UP[u][0] = fa, Tin[u] = ++Timer;
for (int i = 1; i <= L; ++i) UP[u][i] = UP[UP[u][i - 1]][i - 1];
for (const Edge &e : G[u])
if (e.v != fa) Dis[e.v] = Dis[u] + e.w, dfs(e.v, u);
Tout[u] = ++Timer;
}
bool isAncestor(int u, int v) { return Tin[u] <= Tin[v] && Tout[u] >= Tout[v]; }
int lca(int u, int v) {
if (isAncestor(v, u)) return v;
if (isAncestor(u, v)) return u;
for (int i = L; i >= 0; --i)
if (!isAncestor(UP[u][i], v)) u = UP[u][i];
return UP[u][0];
}
LL dist(int u, int v) { return (LL)Dis[u] + Dis[v] - Dis[lca(u, v)] * 2ll; }
struct NodeComp {
bool operator()(int u, int v) const { return Tin[u] < Tin[v]; }
};
set<int, NodeComp> S;
typedef set<int, NodeComp>::iterator SIT;
inline SIT leftOf(SIT it) {
if (it == S.begin()) return --S.end();
return --it;
}
inline SIT rightOf(SIT it) {
if (++it == S.end()) return S.begin();
return it;
}
inline LL diff(int u) {
SIT i = S.find(u), r = rightOf(i), l = leftOf(i);
return dist(u, *l) + dist(u, *r) - dist(*l, *r);
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> N >> M, Timer = 0, L = ceil(log2(N));
for (int i = 1, u, v, w; i <= N - 1; ++i)
cin >> u >> v >> w, G[u].push_back({v, w}), G[v].push_back({u, w});
dfs(1, 1);
LL ans = 0;
for (int i = 1, u; i <= M; ++i) {
cin >> u;
if (S.count(u))
ans -= diff(u), S.erase(u);
else
S.insert(u), ans += diff(u);
cout << ans << endl;
}
return 0;
}

## Bessie’s Snow Cow¶

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, q;
struct bit {
int t[N];
void add(int x, int v) {
for (int i = x; i <= n; i += i & -i) t[i] += v;
}
int qry(int x) {
int res = 0;
for (int i = x; i; i -= i & -i) res += t[i];
return res;
}
} t1, t2;
struct edge {
int to, nxt;
} e[N << 1];
void add(int u, int v) {
}
set<int> s[N];
set<int>::iterator it;
int dfn[N], siz[N], id[N], tim;
void dfs(int u, int fa) {
dfn[u] = ++tim, id[tim] = u, siz[u] = 1;
for (int i = head[u], v; i; i = e[i].nxt) {
v = e[i].to;
if (v == fa) continue;
dfs(v, u);
siz[u] += siz[v];
}
}
int main() {
cin >> n >> q;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
}
dfs(1, 0);
for (int i = 1, opt, u, c; i <= q; i++) {
cin >> opt >> u;
if (opt == 1) {
cin >> c;
it = s[c].lower_bound(dfn[u]);
if (it != s[c].begin() &&
dfn[id[*prev(it)]] + siz[id[*prev(it)]] >= dfn[u] + siz[u])
continue;
while (it != s[c].end() && *it < dfn[u] + siz[u])
} else
printf("%d\n", siz[u] * t1.qry(dfn[u]) + t2.qry(dfn[u] + siz[u] - 1) -
t2.qry(dfn[u]));
}
return 0;
}

## Bessie’s snow cow¶

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, q;
struct bit {
int t[N];
void add(int x, int v) {
for (int i = x; i <= n; i += i & -i) t[i] += v;
}
int qry(int x) {
int res = 0;
for (int i = x; i; i -= i & -i) res += t[i];
return res;
}
} t1, t2;
struct edge {
int to, nxt;
} e[N << 1];
void add(int u, int v) {
}
set<int> s[N];
set<int>::iterator it;
int dfn[N], siz[N], id[N], tim;
void dfs(int u, int fa) {
dfn[u] = ++tim, id[tim] = u, siz[u] = 1;
for (int i = head[u], v; i; i = e[i].nxt) {
v = e[i].to;
if (v == fa) continue;
dfs(v, u);
siz[u] += siz[v];
}
}
int main() {
cin >> n >> q;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
}
dfs(1, 0);
for (int i = 1, opt, u, c; i <= q; i++) {
cin >> opt >> u;
if (opt == 1) {
cin >> c;
it = s[c].lower_bound(dfn[u]);
if (it != s[c].begin() &&
dfn[id[*prev(it)]] + siz[id[*prev(it)]] >= dfn[u] + siz[u])
continue;
while (it != s[c].end() && *it < dfn[u] + siz[u])
} else
printf("%d\n", siz[u] * t1.qry(dfn[u]) + t2.qry(dfn[u] + siz[u] - 1) -
t2.qry(dfn[u]));
}
return 0;
}

## Regions¶

// IOI 2009 Regions

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef long long ll;
struct Emp {
int tin, reg;
vi ch;  // 被指导的
};
struct Reg {
vi ids;             // 其中的Employee
vector<pi> ranges;  // {id, cnt}
int cnt;
};
vector<Emp> ES;
vector<Reg> RS;
void dfs(int u, int &timer) {
auto &r = RS[ES[u].reg];
r.ids.push_back(timer++), r.ranges.push_back({timer, ++r.cnt});
for (int v : ES[u].ch) dfs(v, timer);
r.ranges.push_back({timer, --r.cnt});
}
ll query_by_id(const Reg &r1, const Reg &r2) {
ll ans = 0;
auto &rv = r1.ranges;
for (int u : r2.ids) {
auto it = lower_bound(begin(rv), end(rv), make_pair(u, INT_MAX));
if (it != rv.begin()) ans += prev(it)->second;
}
return ans;
}
ll query_by_range(const Reg &r1, const Reg &r2) {
ll ans = 0;
const auto &rv = r2.ids;
for (size_t i = 0; i + 1 < r1.ranges.size(); ++i) {
int p1 = r1.ranges[i].first, p2 = r1.ranges[i + 1].first;
auto it1 = lower_bound(begin(rv), end(rv), p1),
it2 = lower_bound(begin(rv), end(rv), p2);
ans += r1.ranges[i].second * (it2 - it1);
}
return ans;
}
ll solve(int r1, int r2) {
static map<pi, ll> M;
pi k(r1, r2);
if (M.count(k)) return M[k];
const Reg &reg1 = RS[r1], &reg2 = RS[r2];
int s1 = reg1.ids.size(), s2 = reg2.ids.size();
int tm1 = (log2(s2) + 2) * s1, tm2 = (log2(s1) + 2) * s2;
ll ans = tm1 < tm2 ? query_by_range(reg1, reg2) : query_by_id(reg1, reg2);
return M[k] = ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, R, Q, timer = 0;
cin >> N >> R >> Q, ES.resize(N), RS.resize(R);
cin >> ES[0].reg, --ES[0].reg;
for (int i = 1, fa; i < N; ++i)
cin >> fa >> ES[i].reg, --ES[i].reg, ES[fa - 1].ch.push_back(i);
dfs(0, timer);
for (int q = 0, r1, r2; q < Q; ++q)
cin >> r1 >> r2, cout << solve(r1 - 1, r2 - 1) << endl;
return 0;
}

## Diverging Directions¶

#include <bits/stdc++.h>
using namespace std;
struct Edge {
int v, w;
};
typedef vector<int> vi;
const int VV = 1e6 + 4, INF = 1e9;
vi G[VV];
vector<Edge> Es;
void addEdge(int u, int v, int w) {
G[u].push_back(Es.size()), Es.push_back({v, w});
}
int Sz[VV], Pw[VV], timer;
int Pre[VV], B[VV], D[VV], Tin[VV], Tout[VV];
struct SegTree {
inline void maintain(int o) { minv[o] = min(minv[2 * o], minv[2 * o + 1]); }
void build(int o, int L, int R) {
if (L == R) {
minv[o] = B[Pre[L]] + D[Pre[L]];
return;
}
int lc = 2 * o, rc = 2 * o + 1, m = (L + R) / 2;
build(lc, L, m), build(rc, m + 1, R), maintain(o);
}
inline void pushdown(int o) {
int &a = addv[o], lc = 2 * o, rc = 2 * o + 1;
if (a == 0) return;
addv[lc] += a, addv[rc] += a, minv[lc] += a, minv[rc] += a;
a = 0;
}
int querymin(int o, int L, int R, int ql, int qr) {
int lc = 2 * o, rc = 2 * o + 1, m = (L + R) / 2;
if (L > qr || R < ql) return INF;
if (L >= ql && R <= qr) return minv[o];
pushdown(o);
return min(querymin(lc, L, m, ql, qr), querymin(rc, m + 1, R, ql, qr));
}
void add(int o, int L, int R, int ql, int qr, int v) {
if (L > qr || R < ql) return;
if (L >= ql && R <= qr) return (void)(minv[o] += v, addv[o] += v);
int lc = 2 * o, rc = 2 * o + 1, m = (L + R) / 2;
pushdown(o);
add(lc, L, m, ql, qr, v), add(rc, m + 1, R, ql, qr, v);
maintain(o);
}
};
void dfs(int u, int fa) {
Tin[u] = ++timer, Pre[timer] = u;
for (int ei : G[u]) {
const Edge &e = Es[ei];
if (e.v == fa) continue;
D[e.v] = D[u] + e.w, Pw[e.v] = e.w, dfs(e.v, u);
}
Tout[u] = timer;
}
SegTree S;
int N, M;
inline int getD(int x) { return S.querymin(1, 1, N, Tin[x], Tin[x]) - B[x]; }
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for (int i = 1, u, v, w; i < N; ++i) cin >> u >> v >> w, addEdge(u, v, w);
vi E(2 * N);
for (int i = N, u, v, w; i <= 2 * N - 2; ++i)
cin >> u >> v >> w, B[u] = w, E[i] = u;
dfs(1, 0), S.build(1, 1, N);
while (M--) {
int o, i, w, u, v;
cin >> o;
if (o == 1) {
cin >> i >> w;
if (i >= N)
u = E[i], S.add(1, 1, N, Tin[u], Tin[u], w - B[u]), B[u] = w;
else
u = Es[i - 1].v, S.add(1, 1, N, Tin[u], Tout[u], w - Pw[u]), Pw[u] = w;
} else {
cin >> u >> v;
if (Tin[u] <= Tin[v] && Tin[v] <= Tout[u])
cout << getD(v) - getD(u) << endl;
else
cout << S.querymin(1, 1, N, Tin[u], Tout[u]) - getD(u) + getD(v)
<< endl;
}
}
}