#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#include <bits/stdc++.h>
using namespace std ;
const int MAX = 3e4 + 10 ;
int arr[MAX] ;
int n , m , q ;
vector< vector<int> >adj(MAX) ;
int tim = 0 ;
int in[MAX] , out[MAX] , P[MAX][16] ;
int dep[MAX] ;
int bit[22][22][2*MAX] ;
void Add(int a , int b , int x , int val)
{
for(int i = x ; i <= 2*n ; i += (i & (-i)))
bit[a][b][i] += val ;
}
int Query(int a , int b , int x)
{
int cnt = 0 ;
for(int i = x ; i ; i -= (i & (-i)))
cnt += bit[a][b][i] ;
return cnt ;
}
void dfs(int node , int par)
{
in[node] = ++tim ;
P[node][0] = par ;
for(int j = 1 ; j < 16 ; ++j)
P[node][j] = P[P[node][j-1]][j-1] ;
for(auto &child : adj[node])
{
if(child == par)
continue ;
dep[child] = dep[node] + 1 ;
dfs(child , node) ;
}
out[node] = ++tim ;
}
int LCA(int x , int y)
{
if(dep[x] < dep[y])
swap(x , y) ;
for(int j = 15 ; j >= 0 ; --j)
{
if(dep[x] - (1 << j) >= dep[y])
x = P[x][j] ;
}
if(x == y)
return x ;
for(int j = 15 ; j >= 0 ; --j)
{
if(P[x][j] != P[y][j])
x = P[x][j] , y = P[y][j] ;
}
return P[x][0] ;
}
vector<int> getPath(int x , int y)
{
vector<int>v1 , v2 ;
int lca = LCA(x , y) ;
while(x != lca)
v1.push_back(x) , x = P[x][0] ;
v1.push_back(lca) ;
while(y != lca)
v2.push_back(y) , y = P[y][0] ;
reverse(v2.begin() , v2.end()) ;
for(auto &i : v2)
v1.push_back(i) ;
return v1 ;
}
void modify(int x , int y , int val)
{
vector<int>v = getPath(x , y) ;
for(int i = 0 ; i < v.size() ; ++i)
{
Add(v.size() , i , in[v[i]] , val) ;
Add(v.size() , i , out[v[i]] , -val) ;
}
}
long long solve(int x , int y , int t)
{
if(t < 0)
return 0ll ;
int lca = LCA(x , y) ;
long long cnt = 0 ;
for(int i = 1 ; i <= 20 ; ++i)
{
for(int j = 0 ; j < min(i , t+1) ; ++j)
{
long long a = 1ll + (t - j) / i ;
long long b = Query(i , j , in[x]) - Query(i , j , in[P[lca][0]]) ;
b += Query(i , j , in[y]) - Query(i , j , in[lca]) ;
cnt += a * b ;
}
}
return cnt ;
}
int main()
{
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
cin>>n ;
for(int i = 0 ; i < n-1 ; ++i)
{
int x , y ;
cin>>x>>y ;
adj[x].push_back(y) ;
adj[y].push_back(x) ;
}
dfs(1 , -1) ;
cin>>m ;
for(int i = 0 ; i < m ; ++i)
{
int x , y ;
cin>>x>>y ;
modify(x , y , 1) ;
}
cin>>q ;
while(q--)
{
int ty ;
cin>>ty ;
if(ty == 1)
{
int x , y ;
cin>>x>>y ;
modify(x , y , 1) ;
}
else if(ty == 2)
{
int x , y ;
cin>>x>>y ;
modify(x , y , -1) ;
}
else if(ty == 3)
{
int x , y , l , r ;
cin>>x>>y>>l>>r ;
cout<<solve(x , y , r) - solve(x , y , l-1)<<"\n" ;
}
}
return 0 ;
}
Compilation message
traffickers.cpp: In function 'void modify(int, int, int)':
traffickers.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
86 | for(int i = 0 ; i < v.size() ; ++i)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2028 KB |
Output is correct |
| 2 |
Correct |
6 ms |
3820 KB |
Output is correct |
| 3 |
Correct |
7 ms |
3820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
223 ms |
19820 KB |
Output is correct |
| 2 |
Correct |
224 ms |
18028 KB |
Output is correct |
| 3 |
Correct |
197 ms |
19308 KB |
Output is correct |
| 4 |
Correct |
226 ms |
19948 KB |
Output is correct |
| 5 |
Correct |
231 ms |
19692 KB |
Output is correct |
| 6 |
Correct |
230 ms |
19948 KB |
Output is correct |
| 7 |
Correct |
232 ms |
19820 KB |
Output is correct |
| 8 |
Correct |
180 ms |
19948 KB |
Output is correct |
| 9 |
Correct |
161 ms |
20076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2609 ms |
55148 KB |
Output is correct |
| 2 |
Correct |
2703 ms |
56116 KB |
Output is correct |
| 3 |
Correct |
2494 ms |
55572 KB |
Output is correct |
| 4 |
Correct |
2860 ms |
54648 KB |
Output is correct |
| 5 |
Correct |
3170 ms |
54252 KB |
Output is correct |
| 6 |
Correct |
2593 ms |
56028 KB |
Output is correct |
| 7 |
Correct |
2491 ms |
56084 KB |
Output is correct |
| 8 |
Correct |
2398 ms |
55600 KB |
Output is correct |
