// Author: Ștefan Constantin-Buliga
#include <fstream>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <bitset>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <set>
#include <complex>
using namespace std;
const int SIZE = 1 << 10;
int pointer = SIZE;
char buffer[SIZE];
char Advance() {
if (pointer == SIZE) {
fread(buffer, 1, SIZE, stdin);
pointer = 0;
}
return buffer[pointer++];
}
int Read() {
int answer = 0;
char ch = Advance();
while (!isdigit(ch))
ch = Advance();
while (isdigit(ch)) {
answer = answer * 10 + ch - '0';
ch = Advance();
}
return answer;
}
const int MAXN = 30000;
const int MAXLOG = 14;
const int MAXD = 20;
const int MAXNODES = 131072;
vector<int> g[1 + MAXN];
int dad[1 + MAXLOG][1 + MAXN], depth[1 + MAXN], first[1 + MAXN], last[1 + MAXN], number = 0;
void DFS(int node, int father) {
number++;
first[node] = number;
dad[0][node] = father;
depth[node] = depth[father] + 1;
for (int i = 1; (1 << i) < depth[node]; i++)
dad[i][node] = dad[i - 1][dad[i - 1][node]];
for (auto &son : g[node])
if (son != father)
DFS(son, node);
number++;
last[node] = number;
}
int Raise(int node, int delta) {
if (delta < 0)
return 0;
for (int i = 0; i <= MAXLOG; i++)
if (delta & (1 << i))
node = dad[i][node];
return node;
}
int Lca(int a, int b) {
if (depth[a] < depth[b])
swap(a, b);
a = Raise(a, depth[a] - depth[b]);
if (a == b)
return a;
for (int i = MAXLOG; i >= 0; i--)
if (dad[i][a] != dad[i][b]) {
a = dad[i][a];
b = dad[i][b];
}
return dad[0][a];
}
struct Treap {
int value;
int priority;
int add;
int sum;
Treap *left, *right;
Treap() {
value = 0;
add = 0;
sum = 0;
priority = -1;
left = right = NULL;
}
Treap(int _value, int _priority, int _add, Treap *_left, Treap *_right) {
value = _value;
priority = _priority;
add = _add;
left = _left;
right = _right;
Update();
}
void Update() {
sum = left->sum + right->sum + add;
}
};
Treap *nil, *tree[1 + MAXD][1 + MAXNODES];
pair<Treap*, Treap*> Split(Treap *node, int value) {
if (node == nil)
return make_pair(nil, nil);
if (node->value <= value) {
pair<Treap*, Treap*> temp = Split(node->right, value);
node->right = temp.first;
node->Update();
return make_pair(node, temp.second);
}
else {
pair<Treap*, Treap*> temp = Split(node->left, value);
node->left = temp.second;
node->Update();
return make_pair(temp.first, node);
}
}
Treap* Join(Treap *left, Treap *right) {
if (left == nil)
return right;
if (right == nil)
return left;
if (left->priority > right->priority) {
left->right = Join(left->right, right);
left->Update();
return left;
}
else {
right->left = Join(left, right->left);
right->Update();
return right;
}
}
void Initialize() {
for (int i = 1; i <= MAXD; i++)
for (int j = 1; j <= MAXNODES; j++)
tree[i][j] = nil;
}
bool Find(Treap *node, int value) {
if (node == nil)
return false;
if (node->value == value)
return true;
if (value < node->value)
return Find(node->left, value);
else
return Find(node->right, value);
}
Treap* Insert(Treap *node, int value, int priority, int add) {
if (priority < node->priority) {
if (value < node->value)
node->left = Insert(node->left, value, priority, add);
else
node->right = Insert(node->right, value, priority, add);
node->Update();
return node;
}
pair<Treap*, Treap*> temp = Split(node, value);
return new Treap(value, priority, add, temp.first, temp.second);
}
Treap *Erase(Treap *node, int value, int add) {
if (node->value == value) {
node->add += add;
node->Update();
if (node->add == 0)
node = Join(node->left, node->right);
return node;
}
if (value < node->value)
node->left = Erase(node->left, value, add);
else
node->right = Erase(node->right, value, add);
node->Update();
return node;
}
void Update(int id, int node, int left, int right, int where, int t, int add) {
if (!Find(tree[id][node], t))
tree[id][node] = Insert(tree[id][node], t, rand(), add);
else
tree[id][node] = Erase(tree[id][node], t, add);
if (left == right)
return;
int middle = (left + right) / 2;
if (where <= middle)
Update(id, 2 * node, left, middle, where, t, add);
else
Update(id, 2 * node + 1, middle + 1, right, where, t, add);
}
void AddTraficker(int a, int b, int add) {
int c = Lca(a, b), d = depth[a] - depth[c] + depth[b] - depth[c] + 1;
for (int node = a, t = 0; node != c; node = dad[0][node], t++) {
Update(d, 1, 1, number, first[node], t, add);
Update(d, 1, 1, number, last[node], t, -add);
}
Update(d, 1, 1, number, first[c], depth[a] - depth[c], add);
Update(d, 1, 1, number, last[c], depth[a] - depth[c], -add);
for (int node = b, t = d - 1; node != c; node = dad[0][node], t--) {
Update(d, 1, 1, number, first[node], t, add);
Update(d, 1, 1, number, last[node], t, -add);
}
}
int Query(int id, int node, int left, int right, int from, int to, int x, int y) {
if (from <= left && right <= to) {
pair<Treap*, Treap*> first = Split(tree[id][node], x - 1), second = Split(first.second, y);
int answer = second.first->sum;
tree[id][node] = Join(first.first, Join(second.first, second.second));
return answer;
}
int answer = 0, middle = (left + right) / 2;
if (from <= middle)
answer += Query(id, 2 * node, left, middle, from, to, x, y);
if (middle + 1 <= to)
answer += Query(id, 2 * node + 1, middle + 1, right, from, to, x, y);
return answer;
}
int Get(int a, int b, int c, int d, int temp, int x, int y) {
int answer = 0;
answer += Query(d, 1, 1, number, first[c], first[a], x, y);
if (temp)
answer += Query(d, 1, 1, number, first[temp], first[b], x, y);
return answer;
}
long long GetAnswer(int a, int b, int x, int y) {
int c = Lca(a, b), temp = Raise(b, depth[b] - depth[c] - 1);
long long answer = 0;
for (int d = 1; d <= MAXD; d++) {
if (y - x + 1 <= d && x % d <= y % d) {
answer += Get(a, b, c, d, temp, x % d, y % d);
continue;
}
int x0 = x - x % d + d - 1, y0 = y - y % d;
answer += Get(a, b, c, d, temp, x % d, d - 1) + Get(a, b, c, d, temp, 0, y % d);
if (x0 + 1 <= y0 - 1)
answer += 1LL * ((y0 - x0 - 1) / d) * Get(a, b, c, d, temp, 0, d - 1);
}
return answer;
}
int main() {
//freopen("tema.in", "r", stdin);
//freopen("tema.out", "w", stdout);
nil = new Treap();
nil->left = nil->right = nil;
int n = Read();
for (int i = 1; i < n; i++) {
int a = Read(), b = Read();
g[a].push_back(b);
g[b].push_back(a);
}
DFS(1, 0);
Initialize();
int k = Read();
for (int i = 1; i <= k; i++) {
int a = Read(), b = Read();
AddTraficker(a, b, 1);
}
int q = Read();
for (int i = 1; i <= q; i++) {
int type = Read();
if (type != 3) {
int a = Read(), b = Read();
if (type == 1)
AddTraficker(a, b, 1);
else
AddTraficker(a, b, -1);
}
else {
int a = Read(), b = Read(), x = Read(), y = Read();
printf("%lld\n", GetAnswer(a, b, x, y));
}
}
return 0;
}
Compilation message
traffickers.cpp: In function 'char Advance()':
traffickers.cpp:26:14: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
fread(buffer, 1, SIZE, stdin);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
21880 KB |
Output is correct |
| 2 |
Correct |
46 ms |
25720 KB |
Output is correct |
| 3 |
Correct |
46 ms |
25720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
970 ms |
62840 KB |
Output is correct |
| 2 |
Correct |
1029 ms |
61120 KB |
Output is correct |
| 3 |
Correct |
871 ms |
62156 KB |
Output is correct |
| 4 |
Correct |
972 ms |
63480 KB |
Output is correct |
| 5 |
Correct |
1006 ms |
62328 KB |
Output is correct |
| 6 |
Correct |
990 ms |
62380 KB |
Output is correct |
| 7 |
Correct |
980 ms |
62712 KB |
Output is correct |
| 8 |
Correct |
927 ms |
63096 KB |
Output is correct |
| 9 |
Correct |
896 ms |
63480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3597 ms |
280344 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3612 ms |
284152 KB |
Time limit exceeded |
| 3 |
Execution timed out |
3592 ms |
286588 KB |
Time limit exceeded |
| 4 |
Execution timed out |
3594 ms |
261460 KB |
Time limit exceeded |
| 5 |
Execution timed out |
3590 ms |
192120 KB |
Time limit exceeded |
| 6 |
Execution timed out |
3590 ms |
286232 KB |
Time limit exceeded |
| 7 |
Execution timed out |
3593 ms |
289056 KB |
Time limit exceeded |
| 8 |
Execution timed out |
3597 ms |
288676 KB |
Time limit exceeded |
