QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#468336 | #1163. Another Tree Queries Problem | wcyQwQ | WA | 82ms | 39880kb | C++17 | 4.8kb | 2024-07-08 20:17:07 | 2024-07-08 20:17:07 |
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 = fa[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);
// freopen("A.out", "w", stdout);
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;
int cnt = 0;
while (m--) {
cnt++;
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: 37820kb
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
Wrong Answer
time: 82ms
memory: 39880kb
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 ...
output:
888 1060 857 1885 2402 1434 3152 2493 5111 4257 4865 4303 6631 5609 8038 8003 5024 10067 7827 10311 9185 6416 13348 8960 13915 15773 10755 9819 9335 13519 19030 25686 17257 20116 14163 16681 12619 21088 12962 20909 27312 23188 26558 20851 16866 25900 16023 22896 16727 29074 20920 32392 21428 34998 2...
result:
wrong answer 1st numbers differ - expected: '826', found: '888'