結果
| 問題 |
No.2163 LCA Sum Query
|
| コンテスト | |
| ユーザー |
 to-omer
|
| 提出日時 | 2022-12-18 22:01:46 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 510 ms / 6,000 ms |
| コード長 | 10,071 bytes |
| コンパイル時間 | 1,156 ms |
| コンパイル使用メモリ | 96,316 KB |
| 最終ジャッジ日時 | 2025-02-09 16:30:27 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 40 |
ソースコード
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
using ll = long long;
using namespace std;
#define rep(i, n) for (int i = 0, _rep_ub = (n); i < _rep_ub; i++)
#define fastio \
cin.tie(0); \
ios::sync_with_stdio(0);
// BEGIN: [structure/lct/link-cut-tree-subtree]
// https://ei1333.github.io/library/structure/lct/link-cut-tree-subtree.hpp
template <typename SUM, typename KEY> struct LinkCutTreeSubtree {
struct Node {
Node *l, *r, *p;
KEY key;
SUM sum;
bool rev;
int sz;
bool is_root() const { return !p || (p->l != this && p->r != this); }
Node(const KEY &key, const SUM &sum)
: l(nullptr), r(nullptr), p(nullptr), key(key), sum(sum),
rev(false), sz(1) {}
};
const SUM ident;
LinkCutTreeSubtree(const SUM &ident) : ident(ident) {}
Node *make_node(const KEY &key) {
auto ret = new Node(key, ident);
update(ret);
return ret;
}
Node *set_key(Node *t, const KEY &key) {
expose(t);
t->key = key;
update(t);
return t;
}
void toggle(Node *t) {
swap(t->l, t->r);
t->sum.toggle();
t->rev ^= true;
}
void push(Node *t) {
if (t->rev) {
if (t->l) toggle(t->l);
if (t->r) toggle(t->r);
t->rev = false;
}
}
void update(Node *t) {
t->sz = 1;
if (t->l) t->sz += t->l->sz;
if (t->r) t->sz += t->r->sz;
t->sum.merge(t->key, t->l ? t->l->sum : ident,
t->r ? t->r->sum : ident);
}
void rotr(Node *t) {
auto *x = t->p, *y = x->p;
if ((x->l = t->r)) t->r->p = x;
t->r = x, x->p = t;
update(x), update(t);
if ((t->p = y)) {
if (y->l == x) y->l = t;
if (y->r == x) y->r = t;
update(y);
}
}
void rotl(Node *t) {
auto *x = t->p, *y = x->p;
if ((x->r = t->l)) t->l->p = x;
t->l = x, x->p = t;
update(x), update(t);
if ((t->p = y)) {
if (y->l == x) y->l = t;
if (y->r == x) y->r = t;
update(y);
}
}
void splay(Node *t) {
push(t);
while (!t->is_root()) {
auto *q = t->p;
if (q->is_root()) {
push(q), push(t);
if (q->l == t)
rotr(t);
else
rotl(t);
} else {
auto *r = q->p;
push(r), push(q), push(t);
if (r->l == q) {
if (q->l == t)
rotr(q), rotr(t);
else
rotl(t), rotr(t);
} else {
if (q->r == t)
rotl(q), rotl(t);
else
rotr(t), rotl(t);
}
}
}
}
Node *expose(Node *t) {
Node *rp = nullptr;
for (auto *cur = t; cur; cur = cur->p) {
splay(cur);
if (cur->r) cur->sum.add(cur->r->sum);
cur->r = rp;
if (cur->r) cur->sum.erase(cur->r->sum);
update(cur);
rp = cur;
}
splay(t);
return rp;
}
void link(Node *child, Node *parent) {
expose(child);
expose(parent);
child->p = parent;
parent->r = child;
update(parent);
}
Node *cut(Node *child) {
expose(child);
auto *parent = child->l;
child->l = nullptr;
parent->p = nullptr;
update(child);
return parent;
}
void evert(Node *t) {
expose(t);
toggle(t);
push(t);
}
Node *lca(Node *u, Node *v) {
if (get_root(u) != get_root(v)) return nullptr;
expose(u);
return expose(v);
}
Node *get_kth(Node *x, int k) {
expose(x);
while (x) {
push(x);
if (x->r && x->r->sz > k) {
x = x->r;
} else {
if (x->r) k -= x->r->sz;
if (k == 0) return x;
k -= 1;
x = x->l;
}
}
return nullptr;
}
Node *get_root(Node *x) {
expose(x);
while (x->l) {
push(x);
x = x->l;
}
return x;
}
SUM &query(Node *t) {
expose(t);
return t->sum;
}
};
// END: [structure/lct/link-cut-tree-subtree]
// BEGIN: [tree/levelancestor]
// (https://beet-aizu.github.io/library/tree/levelancestor.cpp)
struct LevelAncestor {
vector<vector<int>> G, par, lad;
vector<int> dep, nxt, len, pth, ord, hs;
LevelAncestor(int n)
: G(n), dep(n), nxt(n, -1), len(n), pth(n), ord(n), hs(n + 1, 0) {
int h = 1;
while ((1 << h) <= n) h++;
par.assign(h, vector<int>(n, -1));
for (int i = 2; i <= n; i++) hs[i] = hs[i >> 1] + 1;
}
void add_edge(int u, int v) {
G[u].emplace_back(v);
G[v].emplace_back(u);
}
void dfs(int v, int p, int d, int f) {
if (nxt[v] < 0) {
par[0][nxt[v] = v] = p;
len[v] = dep[v] = d;
for (int u : G[v]) {
if (u == p) continue;
dfs(u, v, d + 1, 0);
if (len[v] < len[u]) nxt[v] = u, len[v] = len[u];
}
}
if (!f) return;
pth[v] = lad.size();
lad.emplace_back();
for (int k = v;; k = nxt[k]) {
lad.back().emplace_back(k);
pth[k] = pth[v];
if (k == nxt[k]) break;
}
for (;; p = v, v = nxt[v]) {
for (int u : G[v])
if (u != p and u != nxt[v]) dfs(u, v, d + 1, 1);
if (v == nxt[v]) break;
}
}
void build(int r = 0) {
int n = G.size();
dfs(r, -1, 0, 1);
for (int k = 0; k + 1 < (int)par.size(); k++) {
for (int v = 0; v < n; v++) {
if (par[k][v] < 0)
par[k + 1][v] = -1;
else
par[k + 1][v] = par[k][par[k][v]];
}
}
for (int i = 0; i < (int)lad.size(); i++) {
int v = lad[i][0], p = par[0][v];
if (~p) {
int k = pth[p], l = min(ord[p] + 1, (int)lad[i].size());
lad[i].resize(l + lad[i].size());
for (int j = 0, m = lad[i].size(); j + l < m; j++)
lad[i][m - (j + 1)] = lad[i][m - (j + l + 1)];
for (int j = 0; j < l; j++)
lad[i][j] = lad[k][ord[p] - l + j + 1];
}
for (int j = 0; j < (int)lad[i].size(); j++)
if (pth[lad[i][j]] == i) ord[lad[i][j]] = j;
}
}
int lca(int u, int v) {
int h = par.size();
if (dep[u] > dep[v]) swap(u, v);
for (int k = 0; k < h; k++)
if ((dep[v] - dep[u]) >> k & 1) v = par[k][v];
if (u == v) return u;
for (int k = h - 1; k >= 0; k--) {
if (par[k][u] == par[k][v]) continue;
u = par[k][u];
v = par[k][v];
}
return par[0][u];
}
int distance(int u, int v) { return dep[u] + dep[v] - dep[lca(u, v)] * 2; }
int up(int v, int d) {
if (d == 0) return v;
v = par[hs[d]][v];
d -= 1 << hs[d];
return lad[pth[v]][ord[v] - d];
}
// from u to v
int next(int u, int v) {
if (dep[u] >= dep[v]) return par[0][u];
int l = up(v, dep[v] - dep[u] - 1);
return par[0][l] == u ? l : par[0][u];
}
};
// END: [tree/levelancestor]
struct LcaSum {
ll psum, csum, cnt, weight;
ll lsum, lcnt, lcnt2;
LcaSum()
: psum(0), csum(0), cnt(0), weight(0), lsum(0), lcnt(0), lcnt2(0) {}
void toggle() { swap(psum, csum); }
void merge(pair<ll, ll> cost, const LcaSum &parent, const LcaSum &child) {
auto [c, id] = cost;
cnt = parent.cnt + child.cnt + (c > 0) + lcnt;
weight = parent.weight + child.weight + id * lcnt + c;
ll pcnt = parent.cnt + lcnt;
ll pcnt2 = parent.cnt * parent.cnt + lcnt2;
psum = parent.psum + child.psum + lsum;
ll ccnt = child.cnt + lcnt;
ll ccnt2 = child.cnt * child.cnt + lcnt2;
csum = parent.csum + child.csum + lsum;
psum += c * pcnt + id * (pcnt * pcnt - pcnt2) / 2;
csum += c * ccnt + id * (ccnt * ccnt - ccnt2) / 2;
csum += parent.weight * (ccnt + (c > 0));
psum += child.weight * (pcnt + (c > 0));
}
void add(const LcaSum &chsum) {
lsum += chsum.csum;
lcnt += chsum.cnt;
lcnt2 += chsum.cnt * chsum.cnt;
}
void erase(const LcaSum &chsum) {
lsum -= chsum.csum;
lcnt -= chsum.cnt;
lcnt2 -= chsum.cnt * chsum.cnt;
}
} e;
const int MAX = 50050;
using LCT = LinkCutTreeSubtree<LcaSum, pair<ll, ll>>;
LCT::Node *vs[MAX] = {};
int main() {
fastio;
int n, q;
cin >> n >> q;
LCT lct(e);
LevelAncestor la(n + 1);
rep(i, n + 1) vs[i] = lct.make_node({0, i});
la.add_edge(0, 1);
rep(_i, n - 1) {
int a, b;
cin >> a >> b;
lct.evert(vs[b]);
lct.link(vs[b], vs[a]);
la.add_edge(a, b);
}
la.build();
rep(_i, q) {
int u, r, v;
cin >> u >> r >> v;
lct.set_key(vs[u], {u - vs[u]->key.first, u});
lct.evert(vs[r]);
ll p = v != r ? la.next(v, r) : 0;
if (p) {
lct.evert(vs[p]);
lct.cut(vs[v]);
}
LcaSum res = lct.query(vs[v]);
cout << res.csum << '\n';
if (p) {
lct.evert(vs[v]);
lct.link(vs[v], vs[p]);
}
}
return 0;
}