QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#468117 | #1163. Another Tree Queries Problem | _log_ | WA | 0ms | 7692kb | C++14 | 8.2kb | 2024-07-08 19:23:41 | 2024-07-08 19:23:41 |
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;
} 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]; up[p] = 0; sum[lc(p)] += rlen * up[p];
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(Ratio) cout << "update receive " << p << ' ' << pl << ' ' << pr << ' ' << l << ' ' << r << ' ' << x << '\n';
if(l <= pl && pr <= r) {sum[p] += x; tree[p] += x * slen;/* cout << p << ' ' << tree[p] << ' ' << x << '\n'; */return;}
// cout << p << ' ' << pl << ' ' << pr << ' ' << tree[5] << '\n';
push_down(p, pl, pr);
// cout << p << ' ' << pl << ' ' << pr << ' ' << tree[5] << '\n';
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);
// cout << p << ' ' << tree[p] << ' ' << x << '\n';
}
void update1(int p, int pl, int pr, int l, int r, int x) {
if(Ratio) cout << "update1 receive " << p << ' ' << pl << ' ' << pr << ' ' << l << ' ' << r << ' ' << x << '\n';
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(Ratio) cout << "update2 receive " << p << ' ' << pl << ' ' << pr << ' ' << l << ' ' << r << '\n';
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);
}
} using namespace Segment_Tree;
namespace Query {
void modify1(int u, int v) {
ans1 += siz[v]; ans2 += sdep[v];
update1(1, 1, n, dfn[v], dfn[v] + siz[v] - 1, 1);
int pos = fa[u];
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]) {
// cout << "kkk\n";
update(1, 1, n, dfn[top[u]], dfn[u], len); update2(1, 1, n, dfn[top[u]], dfn[u]);
u = fa[top[u]]; len += dfn[u] - dfn[top[u]] + 1;
}
// if(Ratio) cout << "\n\n";
// if(Ratio) cout << "\na\n";
// if(Ratio) cout << "a\n" << len << '\n';
update(1, 1, n, dfn[v], dfn[u], len);
// if(Ratio) cout << "\n\n";
// if(Ratio) print(1, 1, n, 1);
// if(Ratio) cout << "\n\n" << u << ' ' << v << ' ' << dfn[u] << ' ' << dfn[v] << '\n';
// if(Ratio) cout << "b\n";
update2(1, 1, n, dfn[v], dfn[u]);
// if(Ratio) print(1, 1, n, 1);
// if(Ratio) cout << "\n\n";
// if(Ratio) cout << "c " << u << ' ' << v << '\n';
while(pos != 0) update(1, 1, n, dfn[top[pos]], dfn[pos], dep[u] - dep[v] + 1), pos = fa[top[pos]];
// if(Ratio) cout << "chenzhe\n", print(1, 1, n, 1); cout << "\n\n";
}
void modify4(int u, int v) {
int lca = Lca(u, v), pos = lca;
// if(Ratio) print(1, 1, n, 1); cout << "\n\n";
modify3(u, lca); modify3(v, lca); ans2 -= dep[lca]; ans1--;
// if(Ratio) print(1, 1, n, 1); cout << "\n\n";
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;
rep(i, 1, n - 1) cin >> t1 >> t2, add_edge(t1, t2);
dfs(1, 0); dfs2(1, 1);
// debug;
cin >> q;
rep(i, 1, q) {
cin >> op >> t1; if(op != 3) cin >> t2;
// if(i == 3) Ratio = 1;/
if(op == 1) {
if(check(t1, dfn[t2], dfn[t2] + siz[t2] - 1)) modify2(t1, t2);
else modify1(t1, t2);
}
if(op == 2) {
if(dep[t1] < dep[t2]) swap(t1, t2);
modify4(t1, t2);
}
if(op == 3) {
// cout << op << ' ' << t1 << '\n';
cout << query(t1) << '\n';
}
// cerr << "Time = " << i << '\n';
// print(1, 1, n, 0);
// cerr << "\n\n"; cout << "\n\n";
// Ratio = 0;
debug;
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 7692kb
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:
result:
wrong answer Answer contains longer sequence [length = 2], but output contains 0 elements