#include <bits/stdc++.h>
using namespace std;
using i64=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;
}
int 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++)
{
int vv=paths[j][i].query(x,y);
rez+=1LL*vv*((t2/i)+(j<=(t2%i)));
if(t1>=0)
{
rez-=1LL*vv*((t1/i)+(j<=(t1%i)));
}
}
}
cout<<rez<<'\n';
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2140 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2140 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
34 ms |
10840 KB |
Output is correct |
| 2 |
Correct |
33 ms |
9820 KB |
Output is correct |
| 3 |
Correct |
35 ms |
10584 KB |
Output is correct |
| 4 |
Correct |
37 ms |
11072 KB |
Output is correct |
| 5 |
Correct |
39 ms |
10844 KB |
Output is correct |
| 6 |
Correct |
35 ms |
10840 KB |
Output is correct |
| 7 |
Correct |
34 ms |
10840 KB |
Output is correct |
| 8 |
Correct |
38 ms |
10924 KB |
Output is correct |
| 9 |
Correct |
30 ms |
11096 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
512 ms |
32128 KB |
Output is correct |
| 2 |
Correct |
541 ms |
32596 KB |
Output is correct |
| 3 |
Correct |
501 ms |
32336 KB |
Output is correct |
| 4 |
Correct |
479 ms |
31824 KB |
Output is correct |
| 5 |
Correct |
535 ms |
31572 KB |
Output is correct |
| 6 |
Correct |
485 ms |
32592 KB |
Output is correct |
| 7 |
Correct |
341 ms |
32732 KB |
Output is correct |
| 8 |
Correct |
352 ms |
32476 KB |
Output is correct |
