#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 c = 0;
int dist = d[a] + d[b] + 1 - 2 * d[l];
while (a != l) {
for (int j = c; j < dist; ++j)
tr[dist-1][j].add(in[a], dif);
++c;
a = p[a];
}
for (int j = c; j < dist; ++j) {
tr[dist-1][j].add(in[l], dif);
}
c = dist - 1;
while (b != l) {
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 an[20];
static ll difs[20][3];
ans = 0;
for (int i = 2; i <= 20; ++i) {
difs[i-1][0] = (t % i) - 1;
difs[i-1][1] = (z/i) - (t/i);
difs[i-1][2] = z % i;
an[i-1] = 0;
}
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 = 2; i < 21; ++i) {
an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[head[a]], in[a])));
an[i] += ((ll)(tr[i-1][difs[i-1][2]].ask(in[head[a]], in[a])));
if (difs[i-1][0] > -1)
an[i] -= ((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 = 2; i < 21; ++i) {
an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[head[b]], in[b])));
an[i] += ((ll)(tr[i-1][difs[i-1][2]].ask(in[head[b]], in[b])));
if (difs[i-1][0] > -1)
an[i] -= ((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 = 2; i < 21; ++i) {
an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[a], in[b])));
an[i] += ((ll)(tr[i-1][difs[i-1][2]].ask(in[a], in[b])));
if (difs[i-1][0] > -1)
an[i] -= ((ll)(tr[i-1][difs[i-1][0]].ask(in[a], in[b])));
}
for (int i = 2; i < 21; ++i) {
/* cout << an[i-1] << ' '; */
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;
}
Compilation message
traffickers.cpp: In function 'll answer(int, int, int, int)':
traffickers.cpp:216:15: warning: iteration 18 invokes undefined behavior [-Waggressive-loop-optimizations]
216 | an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[a], in[b])));
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffickers.cpp:215:23: note: within this loop
215 | for (int i = 2; i < 21; ++i) {
| ~~^~~~
traffickers.cpp:205:23: warning: iteration 18 invokes undefined behavior [-Waggressive-loop-optimizations]
205 | an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[head[b]], in[b])));
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffickers.cpp:204:31: note: within this loop
204 | for (int i = 2; i < 21; ++i) {
| ~~^~~~
traffickers.cpp:196:23: warning: iteration 18 invokes undefined behavior [-Waggressive-loop-optimizations]
196 | an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[head[a]], in[a])));
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffickers.cpp:195:31: note: within this loop
195 | for (int i = 2; i < 21; ++i) {
| ~~^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
1236 KB |
Output isn't correct |
| 3 |
Incorrect |
5 ms |
1108 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
272 ms |
9548 KB |
Output isn't correct |
| 2 |
Incorrect |
414 ms |
8532 KB |
Output isn't correct |
| 3 |
Incorrect |
56 ms |
9392 KB |
Output isn't correct |
| 4 |
Incorrect |
274 ms |
9732 KB |
Output isn't correct |
| 5 |
Incorrect |
396 ms |
9428 KB |
Output isn't correct |
| 6 |
Incorrect |
364 ms |
9556 KB |
Output isn't correct |
| 7 |
Incorrect |
325 ms |
9428 KB |
Output isn't correct |
| 8 |
Incorrect |
68 ms |
9684 KB |
Output isn't correct |
| 9 |
Incorrect |
41 ms |
9812 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3589 ms |
28040 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3590 ms |
28920 KB |
Time limit exceeded |
| 3 |
Incorrect |
1078 ms |
28408 KB |
Output isn't correct |
| 4 |
Execution timed out |
3600 ms |
27448 KB |
Time limit exceeded |
| 5 |
Incorrect |
3199 ms |
27348 KB |
Output isn't correct |
| 6 |
Incorrect |
1843 ms |
28848 KB |
Output isn't correct |
| 7 |
Incorrect |
434 ms |
29132 KB |
Output isn't correct |
| 8 |
Incorrect |
417 ms |
28620 KB |
Output isn't correct |
