Euler Tourは木を直線にして扱いやすくするテクニックです。
これを使うとLCA、二点間のpathの長さがO(logN)で求められます。
でもHL分解ならあるpath上の辺の長さをすべて+1するみたいなこともできるので、汎用性はHL分解の方が上です。
HL分解は実装が重いというのが弱点ですが、ライブラリ化しているのでわざわざEuler-Tourを使うことはあまりなさそうですね。
オンサイトで持ち込み禁止とかなら(まさにJOI)Euler-Tourを書くけど…JOIerがEuler-Tourを推すのはこのためか…
struct T { pi v; T(pi v = pi(inf, -1)) : v(v) {} T operator+(const T& t) { return T(min(v, t.v)); } friend ostream& operator<<(ostream& out, const T& t) { out << t.v; return out; } }; struct segtree{ int n; vector<T> seg; void init(int mx) { n = 1; while(n < mx) n *= 2; seg = vector<T>(n * 2); } segtree(int mx = 0) { init(mx); } void update(int i, T x) { i += n - 1; seg[i] = x; while(i > 0) { i = (i - 1) / 2; seg[i] = seg[i * 2 + 1] + seg[i * 2 + 2]; } } T ga(int a, int b, int k, int l, int r) { if(b <= l || r <= a) return T(); if(a <= l && r <= b) return seg[k]; else { T lv = ga(a, b, k * 2 + 1, l, (l + r) / 2); T rv = ga(a, b, k * 2 + 2, (l + r) / 2, r); return lv + rv; } } void show() { vector<T> tmp; rep(i, 0, n) tmp.push_back(get(i, i + 1)); debug(tmp); } //edit from here T get(int a, int b) { return ga(a, b, 0, 0, n); } //[a, b) }; struct BIT { //0-origin!!! int n; vi bit0, bit1; void init(int mx) { n = mx; bit0 = vi(n + 1, 0); bit1 = vi(n + 1, 0); } BIT(int mx = 0) { init(mx); } ll ga(vi& bit, int i) { ll s = 0; while(i > 0) { s += bit[i]; i -= i & -i; } return s; } void app(vi& bit, int i, ll x) { while(i <= n) { bit[i] += x; i += i & -i; } } void update(int a, int b, ll x) { //[a, b) a++; app(bit0, a, -x * (a - 1)); app(bit1, a, x); app(bit0, b + 1, x * b); app(bit1, b + 1, -x); } ll get(int a, int b) { //[a, b) a++; return (ga(bit1, b) * b + ga(bit0, b)) - (ga(bit1, a - 1) * (a - 1) + ga(bit0, a - 1)); } }; namespace ET { struct edge { int to, cost; }; int n; vector<edge> G[MAX_N]; int root; int cost[MAX_N * 2]; //2 * n - 2 int vs[MAX_N * 2]; //2 * n - 1 int depth[MAX_N * 2]; //2 * n - 1 int idb[MAX_N], ide[MAX_N]; //(e:v->p)'s cost: cost[idb[v] - 1](>0) or cost[ide[v]](<0) segtree seg; BIT bit; void add_edge(int a, int b, int cost) { G[a].pb(edge{b, cost}); G[b].pb(edge{a, cost}); } void dfs(int v, int p, int d, int pc, int &k) { idb[v] = k; vs[k] = v; depth[k++] = d; rep(i, 0, G[v].size()) { edge& e = G[v][i]; if(e.to == p) continue; cost[k - 1] = e.cost; dfs(e.to, v, d + 1, e.cost, k); vs[k] = v; depth[k++] = d; } if(pc != -1) cost[k - 1] = -pc; ide[v] = k - 1; } void init(int nn, int nroot = 0) { n = nn; root = nroot; int k = 0; dfs(root, -1, 0, -1, k); seg.init(2 * n - 1); rep(i, 0, 2 * n - 1) seg.update(i, T(pi(depth[i], i))); bit.init(2 * n - 2); rep(i, 0, 2 * n - 2) bit.update(i, i + 1, cost[i]); } int lca(int u, int v) { int a = idb[u], b = idb[v]; if(a > b) swap(a, b); return vs[seg.get(a, b + 1).v.sec]; } ll path_cost(int u, int v) { int p = lca(u, v); int a = idb[u], b = idb[p], c = idb[v]; return bit.get(min(a, b), max(a, b)) + bit.get(min(b, c), max(b, c)); } void change_cost(int v, int c) { int a = cost[idb[v] - 1]; cost[idb[v] - 1] = c; cost[ide[v]] = -c; bit.update(idb[v] - 1, idb[v], c - a); bit.update(ide[v], ide[v] + 1, a - c); } void show() { debug("cost", vi(cost, cost + n * 2 - 2)); debug("vs", vi(vs, vs + n * 2 - 1)); debug("depth", vi(depth, depth + n * 2 - 1)); debug("idb", vi(idb, idb + n)); debug("ide", vi(ide, ide + n)); } };