#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int MAXN = 30000;
const int MAXK = 15;
const int MAXD = 20;
struct fenwick {
int fen[2*MAXN];
int reg[2*MAXN];
void add(int val, int id) {
reg[id]+=val;
for (;id<2*MAXN;id=(id|(id+1))) {
fen[id] += val;
}
}
int sm(int id) {
int res = 0;
for (;id>=0;id=(id&(id+1)) - 1) {
res += fen[id];
}
return res;
}
};
fenwick fens[MAXD+1][MAXD+1];
int depth[MAXN];
int timer = 0;
int tin[MAXN];
int tout[MAXN];
vector<int> adj[MAXN];
int up[MAXN][MAXK];
void root(int n, int p, int d) {
up[n][0] = p;
depth[n] = d;
for (int i = 1; i < MAXK; i++) {
up[n][i] = up[up[n][i-1]][i-1];
}
tin[n] = timer++;
for (int e : adj[n]) {
if (e != p) {
root(e, n, d+1);
}
}
tout[n] = timer++;
}
bool is_ancestor(int a, int b) {
return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int lca(int u, int v) {
if (is_ancestor(u, v)) {
return u;
}
else if (is_ancestor(v, u)) {
return v;
}
else {
for (int k = MAXK-1; k >= 0; k--) {
if (!is_ancestor(up[u][k], v)) {
u = up[u][k];
}
}
return up[u][0];
}
}
void upd(int cyc, int offset, int n, bool add) {
if (add) {
fens[cyc][offset].add(1, tin[n]);
fens[cyc][offset].add(-1, tout[n]);
}
else {
fens[cyc][offset].add(-1, tin[n]);
fens[cyc][offset].add(1, tout[n]);
}
}
ll calc(ll t, int u, int v, int lc) {
if (t < 0) {
return 0;
}
ll res = 0;
for (ll cyc = 1; cyc <= MAXD; cyc++) {
for (ll offset = 0; offset < cyc; offset++) {
ll tp = fens[cyc][offset].sm(tin[u]) + fens[cyc][offset].sm(tin[v]) - 2*fens[cyc][offset].sm(tin[lc]) + fens[cyc][offset].reg[tin[lc]];
if (offset <= t) {
res += tp*((t - offset)/cyc + 1);
}
}
}
return res;
}
void chgCyc(int u, int v, bool add) {
int lc = lca(u, v);
int cyc = depth[u] + depth[v] - 2*depth[lc] + 1;
int cnt = 0;
while (u != lc) {
upd(cyc, cnt++, u, add);
u = up[u][0];
}
upd(cyc, cnt, u, add);
cnt = cyc-1;
while (v != lc) {
upd(cyc, cnt--, v,add);
v = up[v][0];
}
}
int main() {
// freopen("input.in", "r", stdin);
cin.tie(0);
cin.sync_with_stdio(0);
int N;
cin >> N;
FR(i, N-1) {
int u, v;
cin >> u >> v;
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
root(0, 0, 0);
int K;
cin >> K;
FR(i, K) {
int u, v;
cin >> u >> v;
u--, v--;
chgCyc(u, v, true);
}
int Q;
cin >> Q;
FR(iter, Q) {
int id, u, v;
cin >> id >> u >> v;
u--, v--;
if (id == 1) {
chgCyc(u, v, true);
}
else if (id == 2) {
chgCyc(u, v, false);
}
else if (id == 3) {
ll t1, t2;
int lc = lca(u, v);
cin >> t1 >> t2;
cout << calc(t2, u, v, lc) - calc(t1-1, u, v, lc) << '\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7532 KB |
Output is correct |
| 2 |
Correct |
13 ms |
9708 KB |
Output is correct |
| 3 |
Correct |
13 ms |
9708 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
240 ms |
39020 KB |
Output is correct |
| 2 |
Correct |
252 ms |
36460 KB |
Output is correct |
| 3 |
Correct |
237 ms |
38764 KB |
Output is correct |
| 4 |
Correct |
255 ms |
39148 KB |
Output is correct |
| 5 |
Correct |
253 ms |
39020 KB |
Output is correct |
| 6 |
Correct |
251 ms |
39168 KB |
Output is correct |
| 7 |
Correct |
243 ms |
38764 KB |
Output is correct |
| 8 |
Correct |
235 ms |
39308 KB |
Output is correct |
| 9 |
Correct |
199 ms |
39276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2754 ms |
104172 KB |
Output is correct |
| 2 |
Correct |
2783 ms |
104888 KB |
Output is correct |
| 3 |
Correct |
2657 ms |
104492 KB |
Output is correct |
| 4 |
Correct |
2933 ms |
103736 KB |
Output is correct |
| 5 |
Correct |
3067 ms |
103568 KB |
Output is correct |
| 6 |
Correct |
2701 ms |
104888 KB |
Output is correct |
| 7 |
Correct |
2689 ms |
104984 KB |
Output is correct |
| 8 |
Correct |
2664 ms |
104636 KB |
Output is correct |
