165D - Beard Graph - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fast                       \
 ios_base::sync_with_stdio(0);      \
 cin.tie(0);                         \
 cout.tie(0);
 
int n,l;
vector<vector<int>> adj;
int timer,sz;
vector<int> tin,tout,dep,a,tree;
vector<vector<int>> up;
 
void dfs1(int v, int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i-1]][i-1];
 
    for (int u : adj[v]) {
        if (u != p)
            dfs1(u, v);
    }
 
    tout[v] = ++timer;
}
 
bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}
 
int lca(int u, int v)
{ 
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = l; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}
 
void preprocess(int root) {
    tin.clear();
    tin.resize(n);
    tout.clear();
    tout.resize(n);
    timer = 0;
    l = ceil(log2(n));
    up.clear();
    up.assign(n, vector<int>(l + 1));
    dfs1(root,root);
}

void bfs(int s){
    vector<bool> vis(n,false);
    vis[s]=true;
    queue<int> q;
    q.push(s);
    dep[s]=0;
    while(q.size()>0){
        int u=q.front();
        q.pop();
        for(auto i:adj[u]){
            if(!vis[i]){
                dep[i]=dep[u]+1;
                vis[i]=true;
                q.push(i);
            }
        }
    }
}
 
int constructST(int ss, int se, int si){
    if(ss==se){
        tree[si]=0;
        return 0;
    }
    int mid=(ss+se)/2;
    tree[si]=constructST(ss,mid,2*si+1)+constructST(mid+1,se,2*si+2);
    return tree[si];
}
 
int getsum(int qs, int qe, int ss, int se, int si){
    if(se<qs || ss>qe) return 0;
    if(qs<=ss && qe>=se) return tree[si];
    int mid=(ss+se)/2;
    int v1=getsum(qs,qe,ss,mid,2*si+1);
    int v2=getsum(qs,qe,mid+1,se,2*si+2);
    return v1+v2;
}
 
void update(int ss, int se, int i, int si, int diff){
    if(i<ss || i>se) return;
    tree[si]=tree[si]+diff;
    if(se>ss){
        int mid=(ss+se)/2;
        update(ss,mid,i,2*si+1,diff);
        update(mid+1,se,i,2*si+2,diff);
    }
}

void dfs2(int x, int p, int& si){
    a[x]=si;
    si++;
    for(auto i:adj[x]){
        if(i!=p){
            dfs2(i,x,si);
        }
    }
}
 
int main(){
    fast;
    int t;
    t=1;
    while(t--){
        cin>>n;
        adj.clear();
        adj.resize(n);
        vector<pair<int,int>> v1;
        for(int i=0;i<n-1;i++){
            int u,v;
            cin>>u>>v;
            u--;
            v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
            v1.push_back({u,v});
        }
        int root=-1;
        for(int i=0;i<n;i++) if((int)adj[i].size()>2) root=i;
        if(root==-1){
            for(int i=0;i<n;i++) if((int)adj[i].size()==1) root=i;
        }
        dep.clear();
        dep.resize(n,0);
        preprocess(root);
        bfs(root);
        sz=0;
        a.clear();
        a.resize(n,0);
        dfs2(root,-1,sz);
        tree.clear();
        tree.resize(4*sz);
        constructST(0,sz-1,0);
        int q;
        cin>>q;
        while(q--){
            int type;
            cin>>type;
            if(type==1){
                int ind;
                cin>>ind;
                ind--;
                int u=v1[ind].first,v=v1[ind].second;
                if(v==lca(u,v)) swap(u,v);
                update(0,sz-1,a[v],0,1);
            }
            else if(type==2){
                int ind;
                cin>>ind;
                ind--;
                int u=v1[ind].first,v=v1[ind].second;
                if(v==lca(u,v)) swap(u,v);
                update(0,sz-1,a[v],0,-1);
            }
            else{
                int u,v;
                cin>>u>>v;
                u--;
                v--;
                int l1=lca(u,v);
                int dist1=dep[l1]+dep[u]-2*dep[lca(l1,u)];
                int dist2=dep[l1]+dep[v]-2*dep[lca(l1,v)];
                int sum1=getsum(a[u]-dist1+1,a[u],0,sz-1,0);
                int sum2=getsum(a[v]-dist2+1,a[v],0,sz-1,0);
                if((sum1+sum2)==0) cout<<dep[u]+dep[v]-2*dep[lca(u,v)]<<endl;
                else cout<<"-1"<<endl;
            }
        }
    }
}