#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define REPD(i, a) for (int i = (a) - 1; i >= 0; --i)
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
/*
Phu Trong from Nguyen Tat Thanh High School for gifted student
*/
template <class X, class Y>
bool minimize(X &x, const Y &y){
X eps = 1e-9;
if (x > y + eps) {x = y; return 1;}
return 0;
}
template <class X, class Y>
bool maximize(X &x, const Y &y){
X eps = 1e-9;
if (x + eps < y) {x = y; return 1;}
return 0;
}
#define MAX 30005
#define LOG 15
int numNode, numQuery;
vector<int> G[MAX];
int up[MAX][LOG], depth[MAX];
int tin[MAX], tout[MAX], timeDfs = 0;
void pre_dfs(int u, int p = -1){
tin[u] = ++timeDfs;
for (int&v : G[u]) if(v ^ p){
depth[v] = depth[u] + 1;
up[v][0] = u;
for (int i = 1; i < LOG; ++i) up[v][i] = up[up[v][i - 1]][i - 1];
pre_dfs(v, u);
}
tout[u] = timeDfs;
}
int lca(int u, int v){
if(depth[u] < depth[v]) swap(u, v);
int dis = depth[u] - depth[v];
for (; dis > 0; dis ^= (dis & -dis)){
int i = __builtin_ctz(dis & -dis);
u = up[u][i];
}
if(u == v) return u;
for (int i = LOG - 1; i >= 0; --i) if(up[u][i] != up[v][i]){
u = up[u][i], v = up[v][i];
}
return up[u][0];
}
struct FenwickTree{
vector<int> F;
int n;
void init(int _n = 0){
this -> n = _n;
F.resize(n + 5);
}
int low_bit (int p){
return p & -p;
}
void upd(int p, int v){
for (; p <= n; p += low_bit(p)) F[p] += v;
}
int ask(int p){
int res = 0;
for (; p > 0; p -= low_bit(p)) res += F[p];
return res;
}
void upd(int l, int r, int v){
upd(l, v); upd(r + 1, -v);
}
} ft[21][21];
void add(int u, int v, int value){
int pa = lca(u, v);
vector<int> nodeu, nodev;
while (u != pa){
nodeu.emplace_back(u);
u = up[u][0];
}
nodeu.emplace_back(pa);
while (v != pa){
nodev.emplace_back(v);
v = up[v][0];
}
reverse(nodev.begin(), nodev.end());
for (int&v : nodev) nodeu.emplace_back(v);
int len = (int)nodeu.size();
for (int i = 0; i < len; ++i){
int u = nodeu[i];
ft[len][i].upd(tin[u], tout[u], value);
}
}
int ask(int u, int v, int T[]){
int pa = lca(u, v);
int ans = 0;
for (int len = 1; len <= 20; ++len){
for (int time = 0; time < len; ++time){
int cover = ft[len][time].ask(tin[u]) + ft[len][time].ask(tin[v]) - ft[len][time].ask(tin[pa]) - ft[len][time].ask(tin[up[pa][0]]);
if(T[1] - time < 0) continue;
int cnt = (T[1] - time) / len + 1;
if(T[0] - time - 1 >= 0){
cnt -= (T[0] - time - 1) / len + 1;
}
ans += cnt * cover;
}
}
return ans;
}
void process(void){
cin >> numNode;
for (int i = 1; i < numNode; ++i){
int u, v; cin >> u >> v;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
pre_dfs(1);
FOR(i, 1, 20) REP(j, i) ft[i][j].init(numNode + 5);
int k; cin >> k;
for (int i = 1; i <= k; ++i){
int u, v; cin >> u >> v;
add(u, v, 1);
}
cin >> numQuery;
for (int i = 1; i <= numQuery; ++i){
int cmd; cin >> cmd;
int u, v; cin >> u >> v;
if(cmd == 1){
add(u, v, 1);
}
if(cmd == 2){
add(u, v, -1);
}
if(cmd == 3){
int T[2]; cin >> T[0] >> T[1];
cout << ask(u, v, T) << '\n';
}
}
}
signed main(){
#define name "Whisper"
cin.tie(nullptr) -> sync_with_stdio(false);
//freopen(name".inp", "r", stdin);
//freopen(name".out", "w", stdout);
process();
return (0 ^ 0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5456 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6992 KB |
Output is correct |
| 3 |
Correct |
4 ms |
6992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
22660 KB |
Output is correct |
| 2 |
Correct |
42 ms |
20816 KB |
Output is correct |
| 3 |
Correct |
45 ms |
22088 KB |
Output is correct |
| 4 |
Correct |
46 ms |
22608 KB |
Output is correct |
| 5 |
Correct |
43 ms |
22612 KB |
Output is correct |
| 6 |
Correct |
45 ms |
22696 KB |
Output is correct |
| 7 |
Correct |
44 ms |
22508 KB |
Output is correct |
| 8 |
Correct |
52 ms |
22740 KB |
Output is correct |
| 9 |
Correct |
38 ms |
23012 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
851 ms |
59324 KB |
Output is correct |
| 2 |
Correct |
922 ms |
59964 KB |
Output is correct |
| 3 |
Correct |
842 ms |
59464 KB |
Output is correct |
| 4 |
Correct |
865 ms |
59180 KB |
Output is correct |
| 5 |
Correct |
885 ms |
58636 KB |
Output is correct |
| 6 |
Correct |
854 ms |
59976 KB |
Output is correct |
| 7 |
Correct |
505 ms |
60052 KB |
Output is correct |
| 8 |
Correct |
621 ms |
59720 KB |
Output is correct |
