#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;
}
/* 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]]) {
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 {
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]];
}
}
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[])
{
if (argc > 1)
freopen(argv[1], "r", stdin);
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 'int32_t main(int, char**)':
traffickers.cpp:229:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
229 | freopen(argv[1], "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
traffickers.cpp: In function 'll answer(int, int, int, int)':
traffickers.cpp:210:15: warning: iteration 18 invokes undefined behavior [-Waggressive-loop-optimizations]
210 | an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[a], in[b])));
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffickers.cpp:209:23: note: within this loop
209 | for (int i = 2; i < 21; ++i) {
| ~~^~~~
traffickers.cpp:201:23: warning: iteration 18 invokes undefined behavior [-Waggressive-loop-optimizations]
201 | an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[head[b]], in[b])));
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffickers.cpp:200:31: note: within this loop
200 | for (int i = 2; i < 21; ++i) {
| ~~^~~~
traffickers.cpp:193:23: warning: iteration 18 invokes undefined behavior [-Waggressive-loop-optimizations]
193 | an[i] += difs[i-1][1] * ((ll)(tr[i-1][i-1].ask(in[head[a]], in[a])));
| ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
traffickers.cpp:192:31: note: within this loop
192 | for (int i = 2; i < 21; ++i) {
| ~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Incorrect |
3 ms |
1236 KB |
Output isn't correct |
| 3 |
Incorrect |
6 ms |
1232 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
251 ms |
9540 KB |
Output isn't correct |
| 2 |
Incorrect |
365 ms |
8536 KB |
Output isn't correct |
| 3 |
Incorrect |
70 ms |
9476 KB |
Output isn't correct |
| 4 |
Incorrect |
315 ms |
9684 KB |
Output isn't correct |
| 5 |
Incorrect |
388 ms |
9428 KB |
Output isn't correct |
| 6 |
Incorrect |
395 ms |
9556 KB |
Output isn't correct |
| 7 |
Incorrect |
295 ms |
9428 KB |
Output isn't correct |
| 8 |
Incorrect |
46 ms |
9684 KB |
Output isn't correct |
| 9 |
Incorrect |
44 ms |
9812 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3580 ms |
28560 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3540 ms |
30668 KB |
Time limit exceeded |
| 3 |
Incorrect |
1042 ms |
29876 KB |
Output isn't correct |
| 4 |
Execution timed out |
3547 ms |
28156 KB |
Time limit exceeded |
| 5 |
Incorrect |
3406 ms |
28812 KB |
Output isn't correct |
| 6 |
Incorrect |
1919 ms |
30432 KB |
Output isn't correct |
| 7 |
Incorrect |
442 ms |
30664 KB |
Output isn't correct |
| 8 |
Incorrect |
454 ms |
30320 KB |
Output isn't correct |
