长链剖分的板子（又是乱搞优化暴力）

对于每一个点，我们定义它深度最深的子节点为它的重儿子（为什么不叫长儿子……），他们之间的连边为重边

然后长链剖分有几个性质

1.总链长为$O(n)$

2.一个节点的$k$级祖先的子树深度必定大于等于当前节点的子树深度

以上两点稍微yy一下就能发现是对的

然后回到这道题。我们设$len[u]$为这一条长链的长度，对于每一个长链的顶点，我们维护它的1到$len[u]$级儿子以及1到$len[u]$级祖先

同时预处理找祖先的倍增数组，并预处理出1到$n$的每一个数字的二进制最高位即$highbit$

那么对于每一个询问$(u,k)$，我们设$r=highbit(k)$，那么我们用预处理的倍增数组让$u$跳到它的$r$级祖先$v$处

因为$k-r<r$，那么$v$的长链的长度$\geq r>k-r$，那么$v$所在的长链预处理的表一定已经包含了$u$的$k$级祖先

时间复杂度为$O(nlogn+m)$，预处理$O(nlogn)$，每一次回答$O(1)$

1 //minamoto 2 #include
     
       3 #include
      
        4 #include
       
         5 using namespace std; 6 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 7 char buf[1<<21],*p1=buf,*p2=buf; 8 int read(){ 9     #define num ch-'0'10     char ch;bool flag=0;int res;11     while(!isdigit(ch=getc()))12     (ch=='-')&&(flag=true);13     for(res=num;isdigit(ch=getc());res=res*10+num);14     (flag)&&(res=-res);15     #undef num16     return res;17 }18 char sr[1<<21],z[20];int C=-1,Z;19 inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}20 void print(int x){21     if(C>1<<20)Ot();if(x<0)sr[++C]=45,x=-x;22     while(z[++Z]=x%10+48,x/=10);23     while(sr[++C]=z[Z],--Z);sr[++C]='\n';24 }25 const int N=3e5+5;26 int head[N],Next[N<<1],ver[N<<1],tot;27 inline void add(int u,int v){28     ver[++tot]=v,Next[tot]=head[u],head[u]=tot;29 }30 int n,md[N],dep[N],fa[N][21],son[N],top[N],len[N],B[N];31 vector
        
          U[N],D[N];32 void dfs(int u,int f){33     md[u]=dep[u]=dep[f]+1,fa[u][0]=f;34     for(int i=1;i<20;++i)35     if(fa[u][i-1]) fa[u][i]=fa[fa[u][i-1]][i-1];36     else break;37     for(int i=head[u];i;i=Next[i]){38         int v=ver[i];39         if(v!=f){40             dfs(v,u);41             if(md[son[u]]
         
          dep[u]) return 0;if(k==0) return u;67     u=fa[u][B[k]],k^=1<