QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#468108 | #1163. Another Tree Queries Problem | _log_ | TL | 0ms | 7812kb | C++14 | 8.2kb | 2024-07-08 19:22:06 | 2024-07-08 19:22:10 |
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7812kb
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 ...