#pragma GCC optimize("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define e1 first
#define e2 second
#define size(x) (int)x.size()
#define all(r) begin(r),end(r)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
//#define time chrono::high_resolution_clock().now().time_since_epoch().count()
#define satori int testCases; cin>>testCases; while(testCases--)
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
///////////////////
#define DEBUG if(1)
///////////////////
const int MAXN=5e4+10;
const int MAXLEN=20;
const int LG=16;
int d[MAXN];
vector<int> g[MAXN];
int p[MAXN];
int par[LG][MAXN];
int t[MAXLEN][MAXLEN][MAXN];
int id[MAXN],sz[MAXN],idc;
void dfs(int u){
id[u]=(++idc);
sz[u]=1;
for(auto v:g[u])
if(p[u]!=v)
par[0][v]=u,p[v]=u,d[v]=d[u]+1,dfs(v),sz[u]+=sz[v];
}
void add(int len,int res,int l,int r){
for(;l<=idc;l=(l|(l-1))+1)
t[len][res][l]++;
r++;
for(;r<=idc;r=(r|(r-1))+1)
t[len][res][r]--;
}
void rem(int len,int res,int l,int r){
for(;l<=idc;l=(l|(l-1))+1)
t[len][res][l]--;
r++;
for(;r<=idc;r=(r|(r-1))+1)
t[len][res][r]++;
}
int get(int len,int res,int p){
int ans=0;
for(;p;p=(p&(p-1)))
ans+=t[len][res][p];
return ans;
}
vector<int> path(int u,int v){
vector<int> lpath,rpath;
while(d[u]>d[v]){
lpath.eb(u);
u=p[u];
}
while(d[v]>d[u]){
rpath.eb(v);
v=p[v];
}
while(u!=v){
lpath.eb(u);
rpath.eb(v);
u=p[u];
v=p[v];
}
lpath.eb(u);
for(auto x:rpath)
lpath.eb(x);
return lpath;
}
int leq(int len,int res,int time){
if(res>time)
return 0;
return 1+(time-res)/len;
}
int get_lca(int u,int v){
if(d[v]>d[u])
swap(u,v);
for(int i=LG-1;i>=0;i--)
if(d[u]-d[v]>=(1<<i))
u=par[i][u];
if(u==v)
return u;
for(int i=LG-1;i>=0;i--){
if(par[i][u]!=par[i][v])
u=par[i][u],v=par[i][v];
}
return par[0][u];
}
int count_path(int u,int v,int len,int res){
int ans=0;
int lca=get_lca(u,v);
ans+=get(len-1,res,id[u])+get(len-1,res,id[v])-get(len-1,res,id[lca]);
if(p[lca]!=0)
ans-=get(len-1,res,id[p[lca]]);
return ans;
}
int32_t main(){
fastio;
int n;
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].eb(v);
g[v].eb(u);
}
dfs(1);
for(int j=1;j<LG;j++)
for(int i=1;i<=n;i++)
par[j][i]=par[j-1][par[j-1][i]];
int k;
cin>>k;
while(k--){
int u,v;
cin>>u>>v;
/*vector<int> pth=path(u,v);
for(int i=0;i<size(pth);i++){
t[size(pth)-1][i][id[pth[i]]]++;
if(id[pth[i]]+sz[pth[i]]<=idc)
t[size(pth)-1][i][id[pth[i]]+sz[pth[i]]]--;
}*/
vector<int> pth=path(u,v);
for(int i=0;i<size(pth);i++)
add(size(pth)-1,i,id[pth[i]],id[pth[i]]+sz[pth[i]]-1);
}
/*for(int i=0;i<MAXLEN;i++)
for(int j=0;j<=i;j++)
for(int l=1;l<=n;l++)
t[i][j][l]+=t[i][j][l&(l-1)];*/
int q;
cin>>q;
while(q--){
int type;
cin>>type;
if(type==1){
int u,v;
cin>>u>>v;
vector<int> pth=path(u,v);
for(int i=0;i<size(pth);i++)
add(size(pth)-1,i,id[pth[i]],id[pth[i]]+sz[pth[i]]-1);
}
else
if(type==2){
int u,v;
cin>>u>>v;
vector<int> pth=path(u,v);
for(int i=0;i<size(pth);i++)
rem(size(pth)-1,i,id[pth[i]],id[pth[i]]+sz[pth[i]]-1);
}
else{
ll ans=0;
int u,v,l,r;
cin>>u>>v>>l>>r;
ll cnt1,cnt2;
for(int i=0;i<MAXLEN;i++){
for(int j=0;j<=i;j++){
cnt1=leq(i+1,j,r)-leq(i+1,j,l-1);
if(cnt1==0)
continue;
cnt2=count_path(u,v,i+1,j);
//if(i+1==3)
//cout<<i+1<<' '<<j<<": "<<cnt1<<' '<<cnt2<<'\n';
ans+=cnt1*cnt2;
}
}
cout<<ans<<'\n';
}
}
return 0;
}
Compilation message
traffickers.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
2 | #pragma GCC optimization ("O3")
|
traffickers.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
3 | #pragma GCC optimization ("unroll-loops")
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2560 KB |
Output isn't correct |
| 2 |
Incorrect |
5 ms |
3564 KB |
Output isn't correct |
| 3 |
Incorrect |
6 ms |
3564 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
150 ms |
12524 KB |
Output isn't correct |
| 2 |
Incorrect |
152 ms |
11372 KB |
Output isn't correct |
| 3 |
Incorrect |
146 ms |
12396 KB |
Output isn't correct |
| 4 |
Incorrect |
162 ms |
12756 KB |
Output isn't correct |
| 5 |
Incorrect |
167 ms |
12396 KB |
Output isn't correct |
| 6 |
Incorrect |
158 ms |
12556 KB |
Output isn't correct |
| 7 |
Incorrect |
157 ms |
12416 KB |
Output isn't correct |
| 8 |
Incorrect |
157 ms |
12652 KB |
Output isn't correct |
| 9 |
Incorrect |
124 ms |
12828 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2056 ms |
34084 KB |
Output isn't correct |
| 2 |
Incorrect |
1953 ms |
35012 KB |
Output isn't correct |
| 3 |
Incorrect |
1985 ms |
34324 KB |
Output isn't correct |
| 4 |
Incorrect |
2051 ms |
33668 KB |
Output isn't correct |
| 5 |
Incorrect |
2196 ms |
33284 KB |
Output isn't correct |
| 6 |
Incorrect |
1917 ms |
35068 KB |
Output isn't correct |
| 7 |
Incorrect |
1780 ms |
35180 KB |
Output isn't correct |
| 8 |
Incorrect |
1798 ms |
34680 KB |
Output isn't correct |
