#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e4+4;
const int N1 = 5e4+4;
struct Bit{
int n,t[N1];
void up(int i,int val){
for (; i<=n; i+=i&-i) t[i] += val;
}
int que(int l,int r){ int ans = 0;
for (; r>0; r-=r&-r) ans += t[r];
for (l--; l>0; l-=l&-l) ans -= t[l];
return ans;
}
} d[20][21];
struct Update{
int t0,r,i,val;
};
struct Query{
int T,i,id,val;
};
int n,n1,n2,k,q;
vector<int> adj[N];
int L[N],R[N],up[N][15];
vector<Update> Qs_U[N];
vector<Query> Qs_Q[N];
ll ans[N1];
void dfs1(int u,int p){ L[u] = n1++, up[u][0] = p;
for (int i=1; i<15; i++) up[u][i] = up[up[u][i-1]][i-1];
for (int v : adj[u]) if (v != p) dfs1(v, u);
R[u] = n1;
}
bool isa(int a,int b){
return L[a] <= L[b] && R[b] <= R[a];
}
int lca(int a,int b){
if (isa(a, b)) return a;
if (isa(b, a)) return b;
for (int i=14; i>=0; i--)
if (!isa(up[a][i], b)) a = up[a][i];
return up[a][0];
}
void add(int a,int b,int id,int val){ vector<int> aux,v;
int l = lca(a, b);
for (; ; a=up[a][0]){ v.push_back(a);
if (a == l) break;
}
for (; b!=l; b=up[b][0]) aux.push_back(b);
reverse(aux.begin(), aux.end());
for (int x : aux) v.push_back(x);
for (int i=0; i<v.size(); i++)
Qs_U[v[i]].push_back({i, int(v.size()), id, val});
}
void dfs2(int u,int p){
for (auto [t0, r, i, val] : Qs_U[u]) d[t0][r].up(i, val);
for (auto [T, i, id, val] : Qs_Q[u]) for (int t0=0; t0<=min(19, T); t0++) for (int r=1; r<=20; r++)
ans[id] += 1ll*val*d[t0][r].que(1, i)*((T-t0)/r + 1);
for (int v : adj[u]) if (v != p) dfs2(v, u);
for (auto [t0, r, i, val] : Qs_U[u]) d[t0][r].up(i, -val);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i=1,a,b; i<n; i++){ cin >> a >> b;
adj[a].push_back(b), adj[b].push_back(a);
}
dfs1(1, 1);
cin >> k;
for (int a,b; k--; ){ cin >> a >> b; add(a, b, 1, 1);}
cin >> q; q++;
for (int t,a,b,t1,t2,i=2; i<=q; i++){ cin >> t >> a >> b;
if (t == 3){ cin >> t1 >> t2;
int l = lca(a, b);
if (t1){
Qs_Q[a].push_back({t1-1, i, n2, -1});
Qs_Q[b].push_back({t1-1, i, n2, -1});
Qs_Q[l].push_back({t1-1, i, n2, 1});
if (l != 1) Qs_Q[up[l][0]].push_back({t1-1, i, n2, 1});
}
Qs_Q[a].push_back({t2, i, n2, 1});
Qs_Q[b].push_back({t2, i, n2, 1});
Qs_Q[l].push_back({t2, i, n2, -1});
if (l != 1) Qs_Q[up[l][0]].push_back({t2, i, n2, -1});
n2++;
}
else add(a, b, i, t==1 ? 1 : -1);
}
for (int t0=0; t0<20; t0++) for (int r=1; r<=20; r++) d[t0][r].n = q;
dfs2(1, -1);
for (int i=0; i<n2; i++) cout << ans[i] << "\n";
return 0;
}
Compilation message
traffickers.cpp: In function 'void add(int, int, int, int)':
traffickers.cpp:63:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int i=0; i<v.size(); i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4180 KB |
Output is correct |
| 2 |
Correct |
6 ms |
4956 KB |
Output is correct |
| 3 |
Correct |
7 ms |
4828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
11896 KB |
Output is correct |
| 2 |
Correct |
141 ms |
11528 KB |
Output is correct |
| 3 |
Correct |
149 ms |
12436 KB |
Output is correct |
| 4 |
Correct |
159 ms |
12224 KB |
Output is correct |
| 5 |
Correct |
155 ms |
11736 KB |
Output is correct |
| 6 |
Correct |
146 ms |
11900 KB |
Output is correct |
| 7 |
Correct |
146 ms |
11880 KB |
Output is correct |
| 8 |
Correct |
159 ms |
12140 KB |
Output is correct |
| 9 |
Correct |
148 ms |
12236 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2877 ms |
70804 KB |
Output is correct |
| 2 |
Correct |
3014 ms |
72100 KB |
Output is correct |
| 3 |
Correct |
2643 ms |
70720 KB |
Output is correct |
| 4 |
Correct |
2813 ms |
69776 KB |
Output is correct |
| 5 |
Correct |
3085 ms |
68340 KB |
Output is correct |
| 6 |
Correct |
2741 ms |
71728 KB |
Output is correct |
| 7 |
Correct |
2304 ms |
71696 KB |
Output is correct |
| 8 |
Correct |
2334 ms |
71060 KB |
Output is correct |
