#include "bits/stdc++.h"
/* #define ONPC */
#define sz(v) ((int)(v.size()))
#define pb push_back
using ll = long long;
using namespace std;
struct aib{
vector<int> f;
int n;
aib (int _n) {
f.assign(_n, 0);
n = _n;
}
void add(int x, int v) {
for (; x < n; x |= (x+1))
f[x] += v;
}
int ask(int x) {
int res = 0;
for (; x >= 0; x = (x&(x+1)) - 1)
res += f[x];
return res;
}
int ask(int l, int r) {
if (l > r)
swap(l,r);
return ask(r) - ask(l-1);
}
};
int n;
vector<int> p;
vector<int> c;
vector<int> hv;
vector<int> head;
vector<int> d;
vector<int> in;
vector<aib> tr[20];
int icnt = 0;
int
lca(int a, int b)
{
while (head[a] != head[b]) {
if (d[head[a]] > d[head[b]])
a = p[head[a]];
else
b = p[head[b]];
}
if (d[a] > d[b])
a = b;
return a;
}
int
dist(int a, int b)
{
return d[a] + d[b] - 2 * d[lca(a,b)] + 1;
}
int
dfs(vector<vector<int>> &adj, int x)
{
int cnt, mcnt = 0;
for (int u : adj[x]) {
if (u == p[x]) continue;
++c[x];
p[u] = x;
d[u] = d[x] + 1;
cnt = dfs(adj,u);
if (cnt > mcnt) {
mcnt = cnt;
hv[x] = u;
}
}
for (int u : adj[x]) {
if (u == p[x]) continue;
}
return c[x];
}
void
dfs_head(vector<vector<int>> &adj, int x, int h)
{
head[x] = h;
in[x] = icnt++;
if (hv[x])
dfs_head(adj,hv[x],h);
for (int u : adj[x]) {
if (u == p[x]) continue;
++c[x];
if (hv[x] != u)
dfs_head(adj,u,u);
}
return;
}
void
addline(int a, int b, int dif)
{
int l = lca(a,b);
int x, c = 0;
int dist = d[a] + d[b] + 1 - 2 * d[l];
x = 1;
while (x * dist < 11)
++x;
while (a != l) {
if (dist > 1 && dist < 11) {
for (int j = c; j < x*dist; ++j) {
if ((j % dist) < c)
tr[x*dist-1][j].add(in[a], (j/dist)*dif);
else
tr[x*dist-1][j].add(in[a], (j/dist + 1)*dif);
}
} else {
for (int j = c; j < dist; ++j)
tr[dist-1][j].add(in[a], dif);
}
++c;
a = p[a];
}
if (dist > 1 && dist < 11) {
for (int j = c; j < x*dist; ++j) {
if ((j % dist) < c)
tr[x*dist-1][j].add(in[l], (j/dist)*dif);
else
tr[x*dist-1][j].add(in[l], (j/dist + 1)*dif);
}
} else {
for (int j = c; j < dist; ++j) {
tr[dist-1][j].add(in[l], dif);
}
}
c = dist - 1;
while (b != l) {
if (dist > 1 && dist < 11) {
for (int j = c; j < x*dist; ++j) {
if ((j % dist) < c)
tr[x*dist-1][j].add(in[b], (j/dist)*dif);
else
tr[x*dist-1][j].add(in[b], (j/dist + 1)*dif);
}
} else {
for (int j = c; j < dist; ++j)
tr[dist-1][j].add(in[b], dif);
}
--c;
b = p[b];
}
return;
}
void
init()
{
vector<vector<int>> adj(n);
int a, b;
for (int i = 0; i < n-1; ++i) {
cin >> a >> b;
--a, --b;
adj[a].pb(b);
adj[b].pb(a);
}
p.assign(n,0);
c.assign(n,0);
d.assign(n,0);
in.assign(n,0);
hv.assign(n,0);
head.assign(n,0);
dfs(adj,0);
dfs_head(adj,0,0);
for (int i = 0; i < 20; ++i) {
for (int j = 0; j < i+1; ++j) {
tr[i].pb(aib(n));
}
}
return;
}
ll
answer(int a, int b, int t, int z)
{
static ll ans;
static ll difs[20][3];
ans = 0;
for (int i = 11; i <= 20; ++i) {
difs[i-1][0] = (t % i) - 1;
difs[i-1][1] = (z/i) - (t/i);
difs[i-1][2] = z % i;
}
difs[0][1] = z-t+1;
/* for (int i = 2; i < 6; ++i) { */
/* cout << difs[i-1][0] << ' ' << difs[i-1][1] << ' ' << difs[i-1][2] << endl; */
/* } */
while (head[a] != head[b]) {
if (d[head[a]] > d[head[b]]) {
ans += difs[0][1] * ((ll)(tr[0][0].ask(in[head[a]], in[a])));
for (int i = 11; i < 21; ++i) {
ans += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[head[a]], in[a])));
ans += ((ll)(tr[i-1][difs[i-1][2]].ask(in[head[a]], in[a])));
if (difs[i-1][0] > -1)
ans -= ((ll)(tr[i-1][difs[i-1][0]].ask(in[head[a]], in[a])));
}
a = p[head[a]];
} else {
ans += difs[0][1] * ((ll)(tr[0][0].ask(in[head[b]], in[b])));
for (int i = 11; i < 21; ++i) {
ans += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[head[b]], in[b])));
ans += ((ll)(tr[i-1][difs[i-1][2]].ask(in[head[b]], in[b])));
if (difs[i-1][0] > -1)
ans -= ((ll)(tr[i-1][difs[i-1][0]].ask(in[head[b]], in[b])));
}
b = p[head[b]];
}
}
ans += difs[0][1] * ((ll)(tr[0][0].ask(in[a], in[b])));
for (int i = 11; i < 21; ++i) {
ans += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[a], in[b])));
ans += ((ll)(tr[i-1][difs[i-1][2]].ask(in[a], in[b])));
if (difs[i-1][0] > -1)
ans -= ((ll)(tr[i-1][difs[i-1][0]].ask(in[a], in[b])));
}
/* for (int i = 2; i < 21; ++i) { */
/* ans += an[i-1]; */
/* } */
/* cout << endl; */
return ans;
}
int32_t
main(int argc, char *argv[])
{
#ifdef ONPC
if (argc > 1)
freopen(argv[1], "r", stdin);
#endif
cin >> n;
init();
int k, q, a, b;
cin >> k;
while (k--) {
cin >> a >> b;
--a, --b;
/* assert(a!=b); */
addline(a,b,1);
}
cin >> q;
int c, t, z;
while (q--) {
cin >> c >> a >> b;
--a, --b;
if (c < 3) {
addline(a,b, (c == 1) ? 1 : -1);
} else {
cin >> t >> z;
cout << answer(a, b, t, z) << endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1236 KB |
Output is correct |
| 3 |
Correct |
5 ms |
1108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
132 ms |
9556 KB |
Output is correct |
| 2 |
Correct |
244 ms |
8568 KB |
Output is correct |
| 3 |
Correct |
63 ms |
9428 KB |
Output is correct |
| 4 |
Correct |
183 ms |
9684 KB |
Output is correct |
| 5 |
Correct |
238 ms |
9488 KB |
Output is correct |
| 6 |
Correct |
209 ms |
9556 KB |
Output is correct |
| 7 |
Correct |
187 ms |
9428 KB |
Output is correct |
| 8 |
Correct |
47 ms |
9688 KB |
Output is correct |
| 9 |
Correct |
39 ms |
9816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3551 ms |
28732 KB |
Time limit exceeded |
| 2 |
Correct |
2510 ms |
29364 KB |
Output is correct |
| 3 |
Correct |
743 ms |
28676 KB |
Output is correct |
| 4 |
Execution timed out |
3557 ms |
28020 KB |
Time limit exceeded |
| 5 |
Correct |
1855 ms |
27616 KB |
Output is correct |
| 6 |
Correct |
1158 ms |
29176 KB |
Output is correct |
| 7 |
Correct |
392 ms |
29424 KB |
Output is correct |
| 8 |
Correct |
379 ms |
28864 KB |
Output is correct |
