#include<bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
const int N = 5e4+5,MXN = 2*N;
vi adj[N];
int n,k,q,tin[N],tout[N],timer,P[N][18],h[N];
void dfs(int v,int p) {
P[v][0] = p;
h[v] = h[p] + 1;
tin[v] = ++timer;
for (int h = 1; h < 18; h++)
P[v][h] = P[ P[v][h-1] ][h-1];
for (int i : adj[v]) {
if (i != p)
dfs(i,v);
}
tout[v] = ++timer;
}
bool isp(int a,int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a,int b) {
if (isp(a,b)) return a;
if (isp(b,a)) return b;
for (int h = 17; h >= 0; h--)
if (!isp(P[a][h],b))
a = P[a][h];
return P[a][0];
}
multiset<pii> s[N];
map<pii,int> mp;
int bit[21][21][N],sum[21][21][N];
void add(int k,int rem,int pos,int val) {
for (;pos < MXN; pos += pos&-pos)
bit[k][rem][pos]+=val;
}
int get(int k,int rem,int pos ) {
int s = 0;
for (;pos;pos-=pos&-pos)
s += bit[k][rem][pos];
return s;
}
void add(int a,int b,int val) {
int c = 0;
int root = lca(a,b);
int k = h[a] - h[root] + h[b] - h[root] + 1;
while (a != root) {
add(k,c,tin[a],val);
add(k,c,tout[a],-val);
sum[k][c][tin[a]] += val;
c++;
a = P[a][0];
}
add(k,c,tin[root],val);
add(k,c,tout[root],-val);
sum[k][c][tin[root]] += val;
c = k-1;
while (b != root) {
sum[k][c][tin[b]] += val;
add(k,c,tin[b],val);
add(k,c,tout[b],-val);
c--;
b = P[b][0];
}
}
int get(int k,int rem,int l,int r) {
return get(k,rem,r) - get(k,rem,l-1);
}
main() {
ios::sync_with_stdio(0);
cin.tie(0);
tout[0] = 1000000000;
cin >> n;
for (int i = 1 ; i < n; i++) {
int a,b;
cin >> a >> b;
adj[a].pb(b);
adj[b].pb(a);
}
dfs(1,0);
cin >> k;
for (int i = 1; i <= k; i++) {
int a,b;
cin >> a >> b;
add(a,b,1);
}cin >> q;
for (int y = 1; y <= q; y++) {
int tp;
cin >> tp;
if (tp == 1) {
int a,b; cin >> a >> b;
add(a,b,1);
}else if (tp == 2) {
int a,b; cin >> a >> b;
add(a,b,-1);
}else {
vi path;
int u,v,t1,t2;
cin >> u >> v >> t1 >> t2;
int root = lca(u,v);
ll ans = 0;
for (int k = 1; k <= 20; k++)
for (int rem = 0; rem < k; rem++)
{
int e = get(k,rem,tin[root],tin[u]);
e += get(k,rem,tin[root],tin[v]);
e -= sum[k][rem][tin[root]];
int b1 = t1;
if ((b1%k) < rem) {
b1 = b1 - (b1%k) + rem;
}
else
if ((b1%k) > rem)b1 = b1- (b1%k) + rem + k;
if (b1 <= t2) {
ans += (ll)e*((t2 - b1 + k )/k);
}
}
cout << ans <<'\n';continue;
}
}
}
Compilation message
traffickers.cpp:79:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
79 | main() {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
12160 KB |
Output is correct |
| 2 |
Correct |
15 ms |
16128 KB |
Output is correct |
| 3 |
Correct |
18 ms |
16256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
210 ms |
63480 KB |
Output is correct |
| 2 |
Correct |
210 ms |
62072 KB |
Output is correct |
| 3 |
Correct |
212 ms |
59768 KB |
Output is correct |
| 4 |
Correct |
223 ms |
64376 KB |
Output is correct |
| 5 |
Correct |
214 ms |
66168 KB |
Output is correct |
| 6 |
Correct |
218 ms |
65372 KB |
Output is correct |
| 7 |
Correct |
211 ms |
63992 KB |
Output is correct |
| 8 |
Correct |
196 ms |
61368 KB |
Output is correct |
| 9 |
Correct |
166 ms |
60784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2049 ms |
159072 KB |
Output isn't correct |
| 2 |
Incorrect |
2164 ms |
154484 KB |
Output isn't correct |
| 3 |
Incorrect |
2009 ms |
151284 KB |
Output isn't correct |
| 4 |
Incorrect |
2133 ms |
165504 KB |
Output isn't correct |
| 5 |
Incorrect |
2366 ms |
169180 KB |
Output isn't correct |
| 6 |
Incorrect |
2157 ms |
152192 KB |
Output isn't correct |
| 7 |
Incorrect |
1820 ms |
141404 KB |
Output isn't correct |
| 8 |
Incorrect |
1763 ms |
146680 KB |
Output isn't correct |
