QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#468388 | #1163. Another Tree Queries Problem | _log_ | WA | 153ms | 11876kb | C++14 | 7.1kb | 2024-07-08 20:35:07 | 2024-07-08 20:35:07 |
Judging History
answer
# include <bits/stdc++.h>
# define rep(i, j, k) for(int i = j; i <= k; ++i)
# define maxn 200100
using namespace std;
int n, q, ans1, ans2;
int op, t1, t2;
namespace Debug {
bool Ratio;
void init() {
if(n <= 5) {cout << "1\n5\n"; exit(0);}
}
} using namespace Debug;
namespace Little_Function {
inline int calc(int l, int r) {return (l + r) * (r - l + 1) / 2;}
inline bool check(int x, int l, int r) {return l <= x && x <= r;}
} using namespace Little_Function;
namespace Tree {
# define go(u) for(int i = head[u], v = to[i]; i; i = nxt[i], v = to[i])
int head[maxn], to[maxn], nxt[maxn], tot;
int fa[maxn], dep[maxn], siz[maxn], son[maxn];
int dfn[maxn], dfn1[maxn], top[maxn], stp;
int sdep[maxn], ssiz[maxn];
inline void add_edge(int u, int v) {
nxt[++tot] = head[u]; to[tot] = v; head[u] = tot;
nxt[++tot] = head[v]; to[tot] = u; head[v] = tot;
}
void dfs(int u, int fat) {
int Max = -1; fa[u] = fat; dep[u] = dep[fat] + 1; siz[u] = 1;
go(u) if(v != fat) dfs(v, u), son[u] = siz[v] > Max ? v : son[u], Max = siz[son[u]], sdep[u] += sdep[v], siz[u] += siz[v];
sdep[u] += dep[u];
}
void dfs2(int u, int tp) {
dfn[u] = ++stp; dfn1[stp] = u; top[u] = tp; ssiz[dfn[u]] = siz[u];
if(son[u]) dfs2(son[u], tp);
go(u) if(!dfn[v]) dfs2(v, v);
}
inline int Lca(int x, int y) {
while(top[x] != top[y]) dep[top[x]] < dep[top[y]] ? y = fa[top[y]] : x = fa[top[x]];
return dep[x] < dep[y] ? x : y;
}
} using namespace Tree;
namespace Segment_Tree {
# define lc(p) (p << 1)
# define rc(p) (p << 1 | 1)
# define mid (pl + pr >> 1)
# define slen (pr - pl + 1)
# define llen (mid - pl + 1)
# define rlen (pr - mid)
# define push_up(p) tree[p] = tree[p << 1] + tree[p << 1 | 1]
int tree[maxn], sum[maxn], tag[maxn], up[maxn];
inline void push_down(int p, int pl, int pr) {
tree[lc(p)] += up[p] * calc(rlen + 1, slen); tree[rc(p)] += up[p] * calc(1, rlen);
up[lc(p)] += up[p]; up[rc(p)] += up[p]; sum[lc(p)] += rlen * up[p]; up[p] = 0;
tree[lc(p)] += sum[p] * llen; tree[rc(p)] += sum[p] * rlen;
sum[lc(p)] += sum[p]; sum[rc(p)] += sum[p]; sum[p] = 0;
tree[lc(p)] += tag[p] * (ssiz[mid] - ssiz[pl - 1]); tree[rc(p)] += tag[p] * (ssiz[pr] - ssiz[mid]);
tag[lc(p)] += tag[p]; tag[rc(p)] += tag[p]; tag[p] = 0;
}
void update(int p, int pl, int pr, int l, int r, int x) {
if(l <= pl && pr <= r) {sum[p] += x; tree[p] += x * slen; return;}
push_down(p, pl, pr);
if(l <= mid) update(lc(p), pl, mid, l, r, x);
if(r > mid) update(rc(p), mid + 1, pr, l, r, x);
push_up(p);
}
void update1(int p, int pl, int pr, int l, int r, int x) {
if(l <= pl && pr <= r) {tag[p] += x; tree[p] += x * (ssiz[pr] - ssiz[pl - 1]); return;}
push_down(p, pl, pr);
if(l <= mid) update1(lc(p), pl, mid, l, r, x);
if(r > mid) update1(rc(p), mid + 1, pr, l, r, x);
push_up(p);
}
void update2(int p, int pl, int pr, int l, int r) {
if(l <= pl && pr <= r) {
up[p]++; sum[p] += r - pr; tree[p] += calc(1, slen) + (r - pr) * slen;
return;
}
push_down(p, pl, pr);
if(l <= mid) update2(lc(p), pl, mid, l, r);
if(r > mid) update2(rc(p), mid + 1, pr, l, r);
push_up(p);
}
int query(int p, int pl, int pr, int l, int r) {
if(l <= pl && pr <= r) return tree[p];
push_down(p, pl, pr); int sum = 0;
if(l <= mid) sum += query(lc(p), pl, mid, l, r);
if(r > mid) sum += query(rc(p), mid + 1, pr, l, r);
return sum;
}
void print(int p, int pl, int pr, bool flag) {
if(flag) cout << p << ' ' << pl << ' ' << pr << ' ' << tree[p] << ' ' << sum[p] << ' ' << tag[p] << ' ' << up[p] << '\n';
else cerr << p << ' ' << pl << ' ' << pr << ' ' << tree[p] << ' ' << sum[p] << ' ' << tag[p] << ' ' << up[p] << '\n';
if(pl != pr) print(lc(p), pl, mid, flag), print(rc(p), mid + 1, pr, flag);
}
void print() {
rep(i, 1, n) cout << query(1, 1, n, i, i) << ' ';
cout << '\n';
}
} using namespace Segment_Tree;
namespace Query {
void modify1(int v) {
int pos = fa[v]; ans1 += siz[v]; ans2 += sdep[v];
update1(1, 1, n, dfn[v], dfn[v] + siz[v] - 1, 1);
while(pos != 0) update(1, 1, n, dfn[top[pos]], dfn[pos], siz[v]), pos = fa[top[pos]];
}
void modify2(int u, int v) {
int pos = u;
if(!check(u, dfn[v] + 1, dfn[v] + siz[son[v]])) while(top[pos] != top[v]) {
pos = top[pos];
if(fa[pos] == v) break;
else pos = fa[pos];
}
else pos = dfn1[dfn[v] + 1]; ans1 += n - siz[pos], ans2 += sdep[1] - sdep[pos];
update1(1, 1, n, 1, n, 1); update1(1, 1, n, dfn[pos], dfn[pos] + siz[pos] - 1, -1);
while(v != 0) update(1, 1, n, dfn[top[v]], dfn[v], -siz[pos]), v = fa[top[v]];
}
void modify3(int u, int v) {
int len = 0, pos = fa[v]; ans1 += dep[u] - dep[v] + 1; ans2 += calc(dep[v], dep[u]);
while(top[u] != top[v]) {
update(1, 1, n, dfn[top[u]], dfn[u], len); update2(1, 1, n, dfn[top[u]], dfn[u]);
len += dfn[u] - dfn[top[u]] + 1; u = fa[top[u]];
}
update(1, 1, n, dfn[v], dfn[u], len);
update2(1, 1, n, dfn[v], dfn[u]);
while(pos != 0) update(1, 1, n, dfn[top[pos]], dfn[pos], dep[u] - dep[v] + 1), pos = fa[top[pos]];
}
void modify4(int u, int v) {
int lca = Lca(u, v), pos = lca;
modify3(u, lca);
modify3(v, lca); ans2 -= dep[lca]; ans1--;
while(pos != 0) update(1, 1, n, dfn[top[pos]], dfn[pos], -1), pos = fa[top[pos]];
}
int query(int u) {
int sum = 0, pos = u;
while(pos != 0) sum += Segment_Tree::query(1, 1, n, dfn[top[pos]], dfn[pos]), pos = fa[top[pos]];
// cout << ans1 << ' ' << ans2 << ' ' << sum << ' ' << dep[u] << ' ' << u << '\n';
return dep[u] * ans1 + ans2 - sum * 2;
}
} using namespace Query;
# define debug cerr << "I Love Furina Forever", exit(0)
signed main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
init();
rep(i, 1, n - 1) cin >> t1 >> t2, add_edge(t1, t2);
dfs(1, 0); dfs2(1, 1);
rep(i, 1, n) ssiz[i] += ssiz[i - 1];
cin >> q;
rep(i, 1, q) {
cin >> op >> t1; if(op != 3) cin >> t2;
if(i == 3) Ratio = 1;
if(op == 1) {
if(t1 == t2) modify1(1);
else if(check(dfn[t1], dfn[t2], dfn[t2] + siz[t2] - 1)) modify2(t1, t2);
else modify1(t2);
}
if(op == 2) {
if(dep[t1] < dep[t2]) swap(t1, t2);
modify4(t1, t2);
}
if(op == 3) {
cout << query(t1) << '\n';
}
// cout << ans1 << ' ' << ans2 << '\n';
// print();
// if(i == 3) debug;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3632kb
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: 153ms
memory: 11876kb
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:
838 980 819 1841 2368 1400 3118 2523 4941 4061 4357 3953 6047 4843 6932 7791 4830 8541 7631 10077 8149 6262 11792 7664 13363 15317 9825 9437 8827 11775 18688 23158 16699 18608 12035 15239 12407 19578 12748 18649 24990 21972 25658 20499 15226 23360 14509 20852 14707 26440 20210 31116 20766 34294 1910...
result:
wrong answer 1st numbers differ - expected: '826', found: '838'