#include <stdio.h>
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
//#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
const ll maxn = 6e4 + 1, maxm = 1e6 + 1;
const ll mod = 1e9 + 7, inf = 1e9, block = 550, hb = 31, base = 1000050017, biginf = 5e18;
const ld eps = 1e-9;
int n, k, q, timer, sz, lac;
int tin[maxn], tout[maxn], up[20][maxn], par[maxn];
vector<int> g[maxn];
void dfs(int v = 1, int p = 0){
up[0][v] = p;
for (int i = 1; i <= 19; ++i){
up[i][v] = up[i - 1][up[i - 1][v]];
}
tin[v] = ++timer;
par[v] = p;
for (auto to : g[v]){
if (to != p){
dfs(to, v);
}
}
tout[v] = ++timer;
}
bool upper(int a, int b){
return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
vector<int> lca(int a, int b){
if (upper(b, a)){
vector<int> vec;
while (a != b){
vec.pb(a);
a = up[0][a];
}
vec.pb(a);
lac = b;
return vec;
}
else if (upper(a, b)){
vector<int> vec;
while (b != a){
vec.pb(b);
b = up[0][b];
}
vec.pb(b);
reverse(vec.begin(), vec.end());
lac = a;
return vec;
}
else{
int v = a;
for (int i = 19; i >= 0; --i){
if (up[i][v] && !upper(up[i][v], b)){
v = up[i][v];
}
}
int lc = up[0][v];
lac = lc;
vector<int> vec;
while (a != lc){
vec.pb(a);
a = up[0][a];
}
vec.pb(lc);
vector<int> vec2;
while (b != lc){
vec2.pb(b);
b = up[0][b];
}
reverse(vec2.begin(), vec2.end());
for (auto it : vec2){
vec.pb(it);
}
return vec;
}
}
struct fenwick{
int f[maxn];
void upd(int pos, int val){
for (int i = pos; i <= timer; i |= (i + 1)){
f[i] += val;
}
}
int get(int pos){
int res = 0;
for (int i = pos; i >= 1; i = (i & (i + 1)) - 1){
res += f[i];
}
return res;
}
} rt[21][20];
ll calc(int x, int d, int p, int y){
ll ky = y / d, k2 = y % d;
ll z = rt[d][p].get(x);
ll sum = ky * z + (k2 >= p) * z;
return sum;
}
ll calc2(int u, int v, int x){
if (x < 0)
return 0;
ll res = 0;
ll parik = par[lac];
for (int i = 1; i <= 20; ++i){
for (int j = 0; j < i; ++j){
ll add = calc(tin[u], i, j, x) + calc(tin[v], i, j, x) - calc(tin[lac], i, j, x);
if (parik > 0){
add -= calc(tin[parik], i, j, x);
}
res += add;
}
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
g[u].pb(v);
g[v].pb(u);
}
dfs();
cin >> k;
for (int i = 1; i <= k; ++i){
int u, v;
cin >> u >> v;
vector<int> kek = lca(u, v);
int len = (int)kek.size();
for (int j = 0; j < len; ++j){
rt[len][j].upd(tin[kek[j]], 1);
rt[len][j].upd(tout[kek[j]], -1);
}
}
cin >> q;
for (int i = 1; i <= q; ++i){
int type;
cin >> type;
int u, v;
cin >> u >> v;
if (type == 1){
vector<int> kek = lca(u, v);
int len = (int)kek.size();
for (int j = 0; j < len; ++j){
rt[len][j].upd(tin[kek[j]], 1);
rt[len][j].upd(tout[kek[j]], -1);
}
}
else if (type == 2){
vector<int> kek = lca(u, v);
int len = (int)kek.size();
for (int j = 0; j < len; ++j){
rt[len][j].upd(tin[kek[j]], -1);
rt[len][j].upd(tout[kek[j]], 1);
}
}
else{
int t, t2;
cin >> t >> t2;
lca(u, v);
ll ans = calc2(u, v, t2) - calc2(u, v, t - 1);
cout << ans << '\n';
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 2 |
Correct |
9 ms |
4564 KB |
Output is correct |
| 3 |
Correct |
11 ms |
4564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
217 ms |
20672 KB |
Output is correct |
| 2 |
Correct |
179 ms |
18788 KB |
Output is correct |
| 3 |
Correct |
225 ms |
20056 KB |
Output is correct |
| 4 |
Correct |
225 ms |
20756 KB |
Output is correct |
| 5 |
Correct |
182 ms |
20632 KB |
Output is correct |
| 6 |
Correct |
212 ms |
20708 KB |
Output is correct |
| 7 |
Correct |
196 ms |
20632 KB |
Output is correct |
| 8 |
Correct |
212 ms |
20844 KB |
Output is correct |
| 9 |
Correct |
303 ms |
20952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3572 ms |
56364 KB |
Time limit exceeded |
| 2 |
Execution timed out |
3597 ms |
56676 KB |
Time limit exceeded |
| 3 |
Execution timed out |
3598 ms |
56216 KB |
Time limit exceeded |
| 4 |
Correct |
2279 ms |
55596 KB |
Output is correct |
| 5 |
Correct |
2279 ms |
55516 KB |
Output is correct |
| 6 |
Execution timed out |
3573 ms |
56816 KB |
Time limit exceeded |
| 7 |
Execution timed out |
3560 ms |
56664 KB |
Time limit exceeded |
| 8 |
Execution timed out |
3575 ms |
56428 KB |
Time limit exceeded |
