#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
int t, n, m, k, a[300010], q, l, r;
vector<int> g[30010];
int tmp=0;
bool vg[30010];
int anc[30010][21];
int ent[30010], ex[30010];
void dfs(int s){
vg[s]=true;
tmp++; ent[s]=tmp;
for(auto u:g[s]){
if(!vg[u]){
anc[u][0]=s;
dfs(u);
}
}
tmp++; ex[s]=tmp;
return;
}
void binary_lifting(){
for(int i=1; i<=19; i++){
for(int j=1; j<=n; j++){
if(anc[j][i-1]>0){
if(anc[anc[j][i-1] ][i-1]>0){
anc[j][i]=anc[anc[j][i-1] ][i-1];
}
}
}
}
return;
}
bool is_anc(int u, int v){
return (ent[u]<=ent[v]) && (ex[u]>=ex[v]);
}
int Lca(int u, int v){
int cr=u;
if(is_anc(u, v) ){return u;}
for(int j=19; j>=0; j--){
if( (anc[cr][j]!=0) && (!is_anc(anc[cr][j], v) ) ){
cr=anc[cr][j];
}
}
return anc[cr][0];
}
int fw[2][200010][21][21];
int fw_q(int u, int i1, int i2, int ext){
int x=ex[u]+1;
int res=0;
for(int i=100000ll-x+1; i>0; i-=(i&(-i))){
res+=fw[ext][i][i1][i2]; //cout<<(i&(-i))<<" "<<flush;
}
//cout<<"x"<<flush;
return res;
}
void fw_u(int u, int i1, int i2, int ext, int upd){
int x;
if(ext==1){
x=ex[u];
}
else{
x=ent[u];
}
for(int i=100000-x+1; i<=100000; i+=(i&(-i))){
fw[ext][i][i1][i2]+=upd;
}
}
int cnt[30010][21][21];
void bandit(int u, int v, int upd){
int lca=Lca(u, v);
int l=1;
int cr=u;
while(cr!=lca){
cr=anc[cr][0];
l++;
}
cr=v;
while(cr!=lca){
cr=anc[cr][0];
l++;
}
cr=u;
int t1=0;
while(cr!=lca){
fw_u(cr, t1, l, 0, upd); fw_u(cr, t1, l, 1, upd); cnt[cr][t1][l]+=upd;
t1++; cr=anc[cr][0];
}
fw_u(cr, t1, l, 0, upd); fw_u(cr, t1, l, 1, upd); cnt[cr][t1][l]+=upd;
cr=v;
t1=0;
while(cr!=lca){
fw_u(cr, l-t1-1, l, 0, upd); fw_u(cr, l-t1-1, l, 1, upd); cnt[cr][l-t1-1][l]+=upd;
t1++; cr=anc[cr][0];
}
//cout<<"bandit: "<<u<<" "<<v<<", period:"<<l<<"\n";
return;
}
int until_t(int res, int i1, int i2, int t){
return res*( ((i1<=t)?(1):(0))+max((t-i1)/i2, 0ll) );
}
int direct_branch(int u, int lca, int t1, int t2){
int res=0;
for(int i=0; i<=20; i++){
for(int j=1; j<=20; j++){
//cout<<"u:"<<u<<" , su="<<(fw_q(u, i, j, 1)-fw_q(u, i, j, 0))<<"... lca="<<lca<<", sl="<<(fw_q(lca, i, j, 1)-fw_q(lca, i, j, 0))<<"\n";
int su=(fw_q(u, i, j, 1)-fw_q(u, i, j, 0)), sl=(fw_q(lca, i, j, 1)-fw_q(lca, i, j, 0));
res+=until_t(su-sl, i, j, t2)-until_t(su-sl, i, j, t1-1);
}
}
//cout<<u<<" "<<lca<<" "<<res<<" t:"<<t1<<" "<<t2<<"q\n";
return res;
}
int query(int u, int v, int t1, int t2){
int res=0;
int lca=Lca(u, v);
//cout<<"nod:"<<u<<", "<<v<<" ; lca:"<<lca<<"\n";
// branch-ul lui u:
res+=direct_branch(u, lca, t1, t2);
//branchul lui v:
res+=direct_branch(v, lca, t1, t2);
//elimin repetarea lui lca:
for(int i=0; i<=20; i++){
for(int j=1; j<=20; j++){
res-=until_t(cnt[lca][i][j], i, j, t2)-until_t(cnt[lca][i][j], i, j, t1-1);
res+=until_t(cnt[u][i][j], i, j, t2)-until_t(cnt[u][i][j], i, j, t1-1);
res+=until_t(cnt[v][i][j], i, j, t2)-until_t(cnt[v][i][j], i, j, t1-1);
}
}
return res;
}
int32_t main(){
INIT
cin>>n;
for(int i=1; i<=(n-1); i++){
int u, v; cin>>u>>v;
g[u].pb(v); g[v].pb(u);
}
dfs(1);
binary_lifting();
cin>>k;
for(int i=1; i<=k; i++){
int u, v; cin>>u>>v;
bandit(u, v, 1);
}
/*for(int i=1; i<=n; i++){
cout<<i<<" ("<<ent[i]<<" "<<ex[i]<<") : ";
for(int j:g[i]){
cout<<j<<" ";
}
cout<<"\n";
}*/
cin>>q;
for(int i=1; i<=q ;i++){
int u, v, t1, t2, tp;
cin>>tp>>u>>v;
if(tp==1){
bandit(u, v, 1);
}
if(tp==2){
bandit(u, v, -1);
}
if(tp==3){
cin>>t1>>t2;
cout<<query(u, v, t1, t2)<<"\n";
}
}
/*for(int i=1; i<=n; i++){
for(int j=0; j<=19; j++){
for(int f=1; f<=20; f++){
int r1=fw_q(i, j, f, 1), r0=fw_q(i, j, f, 0);
if( (r1>0) || (r0>0) ){cout<<"nod="<<i<<" i="<<j<<", j="<<f<<" r1:"<<r1<<" "<<"r0:"<<r0<<"\n";}
}
}
}*/
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1696 KB |
Output is correct |
| 2 |
Correct |
29 ms |
11896 KB |
Output is correct |
| 3 |
Correct |
28 ms |
14080 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
288 ms |
123768 KB |
Output is correct |
| 2 |
Correct |
275 ms |
121848 KB |
Output is correct |
| 3 |
Correct |
310 ms |
107128 KB |
Output is correct |
| 4 |
Correct |
292 ms |
127432 KB |
Output is correct |
| 5 |
Correct |
298 ms |
130560 KB |
Output is correct |
| 6 |
Correct |
294 ms |
129144 KB |
Output is correct |
| 7 |
Correct |
301 ms |
124924 KB |
Output is correct |
| 8 |
Correct |
273 ms |
112504 KB |
Output is correct |
| 9 |
Correct |
258 ms |
107512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2465 ms |
432120 KB |
Output is correct |
| 2 |
Correct |
2519 ms |
386184 KB |
Output is correct |
| 3 |
Correct |
2359 ms |
353984 KB |
Output is correct |
| 4 |
Correct |
2520 ms |
456516 KB |
Output is correct |
| 5 |
Correct |
2636 ms |
447464 KB |
Output is correct |
| 6 |
Correct |
2468 ms |
366312 KB |
Output is correct |
| 7 |
Correct |
2245 ms |
322220 KB |
Output is correct |
| 8 |
Correct |
2265 ms |
322220 KB |
Output is correct |
