#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 <= 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 ) {
// cerr << "For the query: " << u << ' ' << v << ' ' << t << ' ' << l << ": " << sumPath( u, v, l, lca ) << ' ' << sumPath( u, v, t % l, lca ) << endl;
return (long long)(t / l) * sumPath( u, v, l, lca ) + sumPath( u, v, t % l, lca );
}
void updatePath( int u, int v, 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, +1 );
update( t, info[u].finish, -1 );
// cerr << u << ": " << t << endl;
t ++;
}
for ( int t = d; v != lca; v = info[v].p ) {
update( t, info[v].start, +1 );
update( t, info[v].finish, -1 );
// cerr << v << ": " << t << endl;
t --;
}
// cerr << lca << ": " << tLca << endl;
update( tLca, info[lca].start, +1 );
update( tLca, info[lca].finish, -1 );
}
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.lca );
}
}
}
}
for ( int i = 1; i <= cnt; i ++ ) {
cout << answer[i] << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6748 KB |
Output isn't correct |
| 2 |
Incorrect |
5 ms |
7044 KB |
Output isn't correct |
| 3 |
Incorrect |
5 ms |
7000 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
43 ms |
7772 KB |
Output isn't correct |
| 2 |
Incorrect |
36 ms |
7580 KB |
Output isn't correct |
| 3 |
Incorrect |
46 ms |
8276 KB |
Output isn't correct |
| 4 |
Incorrect |
41 ms |
8004 KB |
Output isn't correct |
| 5 |
Incorrect |
37 ms |
7772 KB |
Output isn't correct |
| 6 |
Incorrect |
42 ms |
7768 KB |
Output isn't correct |
| 7 |
Incorrect |
43 ms |
7768 KB |
Output isn't correct |
| 8 |
Incorrect |
44 ms |
8024 KB |
Output isn't correct |
| 9 |
Incorrect |
66 ms |
8020 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
544 ms |
11968 KB |
Output isn't correct |
| 2 |
Incorrect |
678 ms |
12688 KB |
Output isn't correct |
| 3 |
Incorrect |
772 ms |
11956 KB |
Output isn't correct |
| 4 |
Incorrect |
337 ms |
11192 KB |
Output isn't correct |
| 5 |
Incorrect |
281 ms |
11488 KB |
Output isn't correct |
| 6 |
Incorrect |
719 ms |
12728 KB |
Output isn't correct |
| 7 |
Incorrect |
1762 ms |
13092 KB |
Output isn't correct |
| 8 |
Incorrect |
1720 ms |
12332 KB |
Output isn't correct |
