This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using i64=long long;
#define int long long
#define UNUSED -1
#define all(x) x.begin(),x.end()
#define pb push_back
const int mod=1e9+7;
struct Aib
{
int n;
vector<int>aib;
int lsb(int x)
{
return x&(-x);
}
void update(int poz,int val)
{
for(;poz<=n;poz+=lsb(poz))
{
aib[poz]+=val;
}
}
int query(int poz)
{
int rez=0;
for(;poz>0;poz-=lsb(poz))
{
rez+=aib[poz];
}
return rez;
}
void init(int n)
{
this->n=n;
aib.assign(n+1,0);
}
};
const int N=30'000,LG=15;
const int MAX_LEN_PATH=20;
int n;
int tin[N],tout[N],p[N],tt[LG+1][N];
vector<int>adj[N];
void dfs(int nod,int tt)
{
static int timp=0;
tin[nod]=++timp;
p[nod]=tt;
for(auto &c:adj[nod])
{
if(c!=tt)
{
dfs(c,nod);
}
}
tout[nod]=timp;
}
void build()
{
for(int i=0;i<n;i++)
{
tt[0][i]=p[i];
}
for(int i=1;i<=LG;i++)
{
for(int j=0;j<n;j++)
{
tt[i][j]=tt[i-1][tt[i-1][j]];
}
}
}
bool is_parent(int x,int y)
{
return (tin[x]<=tin[y] && tout[y]<=tout[x]);
}
int get_lca(int x,int y)
{
if(is_parent(x,y))
{
return x;
}
if(is_parent(y,x))
{
return y;
}
for(int i=LG;i>=0;i--)
{
if(!is_parent(tt[i][x],y))
{
x=tt[i][x];
}
}
return p[x];
}
struct path_querys
{
Aib aib;
void init()
{
aib.init(n);
}
void add(int nod,int semn)
{
aib.update(tin[nod] , semn);
aib.update(tout[nod]+1 , -semn);
}
int query(int x,int y)
{
int lca=get_lca(x,y);
int now=aib.query(tin[x])+aib.query(tin[y])-aib.query(tin[lca]);
if(lca!=0)
{
now-=aib.query(tin[p[lca]]);
}
return now;
}
}paths[MAX_LEN_PATH][MAX_LEN_PATH+1];
vector<int> get_path(int x,int y)
{
int lca=get_lca(x,y);
vector<int>a,b;
while(x!=lca)
{
a.pb(x);
x=p[x];
}
a.pb(lca);
while(y!=lca)
{
b.pb(y);
y=p[y];
}
reverse(all(b));
for(auto &c:b)
{
a.pb(c);
}
return a;
}
main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<n;i++)
{
int x,y;
cin>>x>>y;
x--;
y--;
adj[x].pb(y);
adj[y].pb(x);
}
dfs(0,0);
build();
for(int i=1;i<=MAX_LEN_PATH;i++)
{
for(int j=0;j<i;j++)
{
paths[j][i].init();
}
}
int k;
cin>>k;
for(int i=0;i<k;i++)
{
int x,y;
cin>>x>>y;
x--;
y--;
auto v=get_path(x,y);
int len=(int)v.size();
for(int i=0;i<len;i++)
{
paths[i][len].add(v[i],1);
}
}
int q;
cin>>q;
while(q--)
{
int cer,x,y;
cin>>cer>>x>>y;
x--;
y--;
if(cer==1)
{
auto v=get_path(x,y);
int len=(int)v.size();
for(int i=0;i<len;i++)
{
paths[i][len].add(v[i],1);
}
}
else if(cer==2)
{
auto v=get_path(x,y);
int len=(int)v.size();
for(int i=0;i<len;i++)
{
paths[i][len].add(v[i],-1);
}
}
else
{
int t1,t2;
cin>>t1>>t2;
t1--;
i64 rez=0;
for(int i=1;i<=MAX_LEN_PATH;i++)
{
for(int j=0;j<i;j++)
{
rez+=1LL*paths[j][i].query(x,y)*((t2/i)+((t2%i)>=j));
}
}
if(t1>=0)
{
for(int i=1;i<=MAX_LEN_PATH;i++)
{
for(int j=0;j<i;j++)
{
rez-=1LL*paths[j][i].query(x,y)*((t1/i)+((t1%i)>=j));
}
}
}
cout<<rez<<'\n';
}
}
}
Compilation message (stderr)
traffickers.cpp:145:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
145 | main()
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |