#include <bits/stdc++.h>
using namespace std;
const int NMAX = 3e4;
const int LMAX = 20;
const int QMAX = 5e4;
vector <int> edges[NMAX + 1];
int aib[LMAX + 1][2 * NMAX + 1];
struct node {
int start;
int finish;
int jump;
int p;
int d;
} info[NMAX + 1];
void update( int l, int c, int x ) {
for ( int i = l; i <= LMAX; i += ( i & -i ) ) {
for ( int j = c; j <= 2 * NMAX; j += ( j & -j ) ) {
aib[i][j] += x;
}
}
}
int sum( int l, int c ) {
int s = 0;
for ( int i = l; i > 0; i -= ( i & -i ) ) {
for ( int j = c; j > 0; j -= ( j & -j ) ) {
s += aib[i][j];
}
}
return s;
}
int t = 0;
void dfs( int node, int p = 1 ) {
info[node].p = p;
info[node].d = info[p].d + 1;
info[node].start = ++t;
for ( auto vec : edges[node] ) {
if ( vec == p ) continue;
dfs( vec, node );
if ( info[p].d - info[info[p].jump].d == info[info[p].jump].d - info[info[info[p].jump].jump].d ) {
info[vec].jump = info[info[p].jump].jump;
} else {
info[vec].jump = p;
}
}
info[node].finish = ++t;
}
bool isAncestor( int u, int v ) {
return ( info[u].start <= info[v].start && info[v].finish <= info[u].finish );
}
int LCA( int u, int v ) {
while ( !isAncestor( u, v ) ) {
if ( !isAncestor( info[u].jump, v ) ) {
u = info[u].jump;
} else {
u = info[u].p;
}
}
return u;
}
int dist( int u, int v, int lca ) {
return info[u].d + info[v].d - 2 * info[lca].d + 1;
}
struct query {
int tip;
int u;
int v;
int t1;
int t2;
int lca;
};
int sumPath( int u, int v, int l, int lca ) {
int s = sum( l, info[u].start ) + sum( l, info[v].start ) - sum( l, info[lca].start );
if ( lca == 1 ) {
return s;
}
return s - sum( l, info[info[lca].p].start );
}
long long queryPath( int u, int v, int l, int lca, int t ) {
return (long long)(t / l) * sumPath( u, v, l, lca ) + sumPath( u, v, t % l, lca );
}
void updatePath( int u, int v, int add, int lca ) {
int d = dist( u, v, lca ), tLca = dist( u, lca, lca );
for ( int t = 1; u != lca; u = info[u].p ) {
update( t, info[u].start, +add );
update( t, info[u].finish, -add );
t ++;
}
for ( int t = d; v != lca; v = info[v].p ) {
update( t, info[v].start, +add );
update( t, info[v].finish, -add );
t --;
}
update( tLca, info[lca].start, +add );
update( tLca, info[lca].finish, -add );
}
long long answer[QMAX + 1];
int main() {
ios_base::sync_with_stdio( false );
cin.tie( NULL );
cout.tie( NULL );
// ifstream cin( "Traffickers.in");
// ofstream cout( "traffickers.out" );
int n, k, q;
cin >> n;
for ( int i = 1, a, b; i < n; i ++ ) {
cin >> a >> b;
edges[a].push_back( b );
edges[b].push_back( a );
}
info[1].jump = 1;
dfs( 1 );
vector <query> v;
cin >> k;
for ( int i = 1, a, b; i <= k; i ++ ) {
cin >> a >> b;
v.push_back( (query){1, a, b, 0, 0, LCA(a, b)} );
}
cin >> q;
for ( int i = 1, a, b, tip; i <= q; i ++ ) {
cin >> tip >> a >> b;
if ( tip == 3 ) {
int t1, t2;
cin >> t1 >> t2;
v.push_back( (query){tip, a, b, t1, t2, LCA(a, b)} );
} else {
v.push_back( (query){tip, a, b, 0, 0, LCA(a, b)} );
}
}
int cnt;
for ( int l = 1; l <= LMAX; l ++ ) {
for ( int i = 1; i <= LMAX; i ++ ) {
for ( int j = 1; j <= 2 * NMAX; j ++ ) {
aib[i][j] = 0;
}
}
cnt = 0;
for ( auto p : v ) {
if ( p.tip == 3 ) {
answer[++cnt] += queryPath( p.u, p.v, l, p.lca, p.t2 + 1 ) - queryPath( p.u, p.v, l, p.lca, p.t1 );
} else {
if ( dist( p.u, p.v, p.lca ) == l ) {
updatePath( p.u, p.v, (p.tip == 1 ? 1 : -1), p.lca );
}
}
}
}
for ( int i = 1; i <= cnt; i ++ ) {
cout << answer[i] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
6748 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7048 KB |
Output is correct |
| 3 |
Correct |
5 ms |
7004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
7912 KB |
Output is correct |
| 2 |
Correct |
35 ms |
7768 KB |
Output is correct |
| 3 |
Correct |
45 ms |
8052 KB |
Output is correct |
| 4 |
Correct |
41 ms |
8028 KB |
Output is correct |
| 5 |
Correct |
37 ms |
7828 KB |
Output is correct |
| 6 |
Correct |
39 ms |
7764 KB |
Output is correct |
| 7 |
Correct |
42 ms |
7940 KB |
Output is correct |
| 8 |
Correct |
49 ms |
8024 KB |
Output is correct |
| 9 |
Correct |
67 ms |
8128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
581 ms |
12076 KB |
Output is correct |
| 2 |
Correct |
711 ms |
12380 KB |
Output is correct |
| 3 |
Correct |
778 ms |
12116 KB |
Output is correct |
| 4 |
Correct |
370 ms |
11316 KB |
Output is correct |
| 5 |
Correct |
340 ms |
10812 KB |
Output is correct |
| 6 |
Correct |
785 ms |
12352 KB |
Output is correct |
| 7 |
Correct |
1801 ms |
12816 KB |
Output is correct |
| 8 |
Correct |
1754 ms |
12080 KB |
Output is correct |
