QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#468287 | #1163. Another Tree Queries Problem | wcyQwQ | TL | 0ms | 41904kb | C++17 | 4.7kb | 2024-07-08 20:08:59 | 2024-07-08 20:08:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 10;
vector<int> g[N];
int son[N], top[N], sz[N], dep[N], fa[N], dfn[N], rk[N], tim, n;
LL sdp[N], ssz[N];
void dfs1(int u, int p) {
fa[u] = p, dep[u] = dep[p] + 1, sz[u] = 1;
for (int v : g[u]) if (v != p) {
dfs1(v, u);
sz[u] += sz[v];
if (sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int t) {
dfn[u] = ++tim, rk[tim] = u, top[u] = t;
if (son[u]) dfs2(son[u], t);
for (int v : g[u]) if (v != son[u] && v != fa[u]) dfs2(v, v);
}
int find(int u, int v) { // the son of u -> v
while (top[u] != top[v]) {
if (fa[top[u]] == v) return top[u];
u = top[u];
}
return son[v];
}
int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
return u;
}
struct Tag {
LL x, y, z;
Tag(LL x = 0, LL y = 0, LL z = 0) : x(x), y(y), z(z) {}
};
struct Node {
LL sum;
Tag tg;
Node(LL sum = 0, Tag tg = Tag()) : sum(sum), tg(tg) {}
};
inline Tag operator+(Tag a, Tag b) { return Tag(a.x + b.x, a.y + b.y, a.z + b.z); }
inline Node operator+(Node a, Node b) { return Node(a.sum + b.sum); }
inline void tag(Node &u, Tag tg, int l, int r) {
u.sum += (ssz[r] - ssz[l - 1]) * tg.x;
u.sum += (sdp[r] - sdp[l - 1]) * tg.y;
u.sum += tg.z * (r - l + 1);
u.tg = u.tg + tg;
}
struct SGT {
Node t[N * 4];
void pushup(int p) { t[p] = t[p * 2] + t[p * 2 + 1]; }
void pushdown(int p, int l, int r) {
int m = (l + r) / 2;
tag(t[p * 2], t[p].tg, l, m);
tag(t[p * 2 + 1], t[p].tg, m + 1, r);
t[p].tg = Tag();
}
void modify(int p, int l, int r, int ql, int qr, Tag tg) {
if (ql <= l && r <= qr) return tag(t[p], tg, l, r);
pushdown(p, l, r);
int m = (l + r) / 2;
if (ql <= m) modify(p * 2, l, m, ql, qr, tg);
if (qr > m) modify(p * 2 + 1, m + 1, r, ql, qr, tg);
pushup(p);
}
void modify(int l, int r, Tag tg) { modify(1, 1, n, l, r, tg); }
LL query(int p, int l, int r, int ql, int qr) {
if (ql > qr) return 0;
if (ql <= l && r <= qr) return t[p].sum;
pushdown(p, l, r);
int m = (l + r) / 2;
if (qr <= m) return query(p * 2, l, m, ql, qr);
if (ql > m) return query(p * 2 + 1, m + 1, r, ql, qr);
return query(p * 2, l, m, ql, qr) + query(p * 2 + 1, m + 1, r, ql, qr);
}
LL query(int l, int r) { return query(1, 1, n, l, r); }
} sgt;
void mPath(int u, int v, Tag tg) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
sgt.modify(dfn[top[u]], dfn[u], tg);
u = fa[top[u]];
}
if (dfn[u] > dfn[v]) swap(u, v);
sgt.modify(dfn[u], dfn[v], tg);
}
LL qPath(int u) {
LL ans = 0;
while (u) {
ans += sgt.query(dfn[top[u]], dfn[u]);
u = fa[top[u]];
}
return ans;
}
int main() {
// freopen("A.in", "r", stdin);
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
dfs1(1, 0), dfs2(1, 1);
for (int i = 1; i <= n; i++) {
sdp[i] = sdp[i - 1] + dep[rk[i]];
ssz[i] = ssz[i - 1] + sz[rk[i]];
}
LL s1 = 0, s2 = 0;
auto calc = [&] (int l, int r) {
return 1ll * (l + r) * (r - l + 1) / 2;
};
int m;
cin >> m;
while (m--) {
int op;
cin >> op;
if (op == 1) {
int u, v;
cin >> u >> v;
if (dfn[v] >= dfn[u] && dfn[v] <= dfn[u] + sz[u] - 1) {
s1 += sz[v];
s2 += sdp[dfn[v] + sz[v] - 1] - sdp[dfn[v] - 1];
sgt.modify(dfn[v], dfn[v] + sz[v] - 1, Tag(1, 0, 0));
} else if (dfn[u] >= dfn[v] && dfn[u] <= dfn[v] + sz[v] - 1) {
int w = find(u, v);
s1 += n - sz[w];
s2 += sdp[n] - sdp[dfn[w] + sz[w] - 1] + sdp[dfn[w] - 1];
sgt.modify(1, n, Tag(1, 0, 0));
sgt.modify(dfn[w], dfn[w] + sz[w] - 1, Tag(-1, 0, 0));
mPath(1, v, Tag(0, 0, -sz[w]));
} else {
s1 += sz[v];
s2 += sdp[dfn[v] + sz[v] - 1] - sdp[dfn[v] - 1];
sgt.modify(dfn[v], dfn[v] + sz[v] - 1, Tag(1, 0, 0));
}
} else if (op == 2) {
int u, v;
cin >> u >> v;
int p = lca(u, v);
s1 += dep[u] + dep[v] - 2 * dep[p] + 1;
s2 += calc(dep[p], dep[u]) + calc(dep[p], dep[v]) - dep[p];
mPath(u, p, Tag(0, -1, dep[u] + 1));
mPath(v, p, Tag(0, -1, dep[v] + 1));
mPath(p, p, Tag(0, 0, -1));
if (p != 1) mPath(1, fa[p], Tag(0, 0, dep[u] + dep[v] - 2 * dep[p] + 1));
} else {
int u;
cin >> u;
cout << s1 * dep[u] + s2 - 2 * qPath(u) << '\n';
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 41904kb
input:
5 4 2 2 5 1 5 1 3 5 2 2 4 3 4 2 1 5 2 5 5 3 2
output:
1 5
result:
ok 2 number(s): "1 5"
Test #2:
score: -100
Time Limit Exceeded
input:
200 171 114 50 183 28 68 67 152 139 125 67 55 50 98 106 71 46 42 157 165 42 49 113 12 81 145 105 13 38 96 34 156 24 17 21 191 135 54 174 116 177 157 123 71 95 130 135 193 150 129 25 190 96 93 188 173 90 160 86 187 20 132 199 75 59 195 189 24 40 68 163 83 25 13 73 33 59 50 154 19 146 21 151 67 89 69 ...