[atcoder1998] stamp Rally

The question

We have a N (3<=N<=10^5) A node and M(N−1≤M≤10^5) An undirected graph of edges . The node number is 1 To N, Side number is 1 To M. edge i Connection nodes ai and bi. Make sure the graph is connected . On this picture ,Q(1≤Q≤10^5) A pair of brothers are participating in a project called Stamp Rally The activities of . The first i Yes Stamp Rally as follows ：
A brother from the node xi Start , Another slave node yi Start .(1≤xi < yi≤N)
Two brothers visit the nodes on the graph along the edge , A total of access zi(3≤zi≤N) Nodes , Including the starting node . ad locum , Even if a node is accessed multiple times , Calculate only once .
Define the score as the maximum number of the edges they cross . Their goal is to minimize this score .
Find out the lowest score for each brother .

Answer key

Add the number of edges to the graph from small to large , Use and collect , Each side added i, Scan all queries , If the size of their Unicom reaches zi, The answer to this question by i.
But this is $O(MQ)$ Of .
Use the whole dichotomy , Add the first half first $[l,mid]$ The edge of , Determine which queries have met the criteria , The answers to these questions must be $\leq mid$, Divide it into the first half , Then restore the merged query set , Recursive processing $[l,mid]$ Of , and $[mid+1,r]$ Of .
In order to restore the merge set , You can use rank consolidation .

Code

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=100005;

int N,M,Q;

struct Edge
{
    int u,v;
}E[MAXN];
struct Query
{
    int x,y,z;
}q[MAXN];
int id[MAXN],tmp[MAXN],mk[MAXN],ans[MAXN];

int stk[MAXN][2],tp;
int fa[MAXN],siz[MAXN];
int Root(int u)
{
    if(fa[u]==0)
        return u;
    return Root(fa[u]);
}
void Union(int u,int v)
{
    int r1=Root(u),r2=Root(v);
    if(r1==r2)
        return;
    if(siz[r1]<siz[r2])
        swap(r1,r2);
    fa[r2]=r1;
    stk[++tp][0]=r2;
    stk[tp][1]=r1;
    siz[r1]+=siz[r2];
}

void solve(int a,int b,int l,int r)
{
    if(a==b)
    {
        for(int i=l;i<=r;i++)
            ans[id[i]]=a;
        Union(E[a].u,E[a].v);
        return;
    }
    tp=0;
    int mid1=(a+b)/2;
    for(int i=a;i<=mid1;i++)
        Union(E[i].u,E[i].v);
    for(int i=l;i<=r;i++)
    {
        int r1=Root(q[id[i]].x),r2=Root(q[id[i]].y);
        if(r1==r2&&siz[r1]>=q[id[i]].z)
            mk[i]=1;
        if(r1!=r2&&siz[r1]+siz[r2]>=q[id[i]].z)
            mk[i]=1;
    }
    int it=l-1;
    for(int i=l;i<=r;i++)
        if(mk[i])
            tmp[++it]=id[i];
    int mid2=it;
    for(int i=l;i<=r;i++)
        if(!mk[i])
            tmp[++it]=id[i];
    for(int i=l;i<=r;i++)
        id[i]=tmp[i],mk[i]=0;
    while(tp)
    {
        fa[stk[tp][0]]=0;
        siz[stk[tp][1]]-=siz[stk[tp][0]];
        tp--;
    }
    solve(a,mid1,l,mid2);
    solve(mid1+1,b,mid2+1,r);
}

int main()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++)
        scanf("%d%d",&E[i].u,&E[i].v);
    scanf("%d",&Q);
    for(int i=1;i<=Q;i++)
        scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].z);
    for(int i=1;i<=N;i++)
        fa[i]=0,siz[i]=1;
    for(int i=1;i<=Q;i++)
        id[i]=i;
    solve(1,M,1,Q);
    for(int i=1;i<=Q;i++)
        printf("%d\n",ans[i]);

    return 0;
}