QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#468284 | #1163. Another Tree Queries Problem | wcyQwQ | WA | 9ms | 38196kb | C++17 | 4.7kb | 2024-07-08 20:08:11 | 2024-07-08 20:08:12 |
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: 0
Wrong Answer
time: 9ms
memory: 38196kb
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:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
wrong answer 1st numbers differ - expected: '1', found: '0'