长者的题qwq

在没有换根之前，都是可以裸的树剖维护的

一个最普通的询问

如果我们换一次根

就会变成一下情况

然而我们所查询的子树的结构并没有发生改变，为什么呢？

我们可以观察到，所查询的根并没有在当前的根到原来跟的路径上。

可以想象成你将所换的根提起来，在提的时候，所有结构发生改变的子树的根，都是所换根到原来根的路径上的节点，因为他们的子树中的节点要成为他们的父节点（or级别更高，不知道高到哪里去了）

就像上面一样

查询时就是查询红线以外的的节点

]

看起来很简单的样子qwq，不就是如果查询节点的\(A\)和当前根节点的\(R\)的\(Lca\)是\(A\)的时候，就查询\(A\)的祖先and其祖先和\(A\)除了\(R\)所在的

子树，以外的所有节点么。

不过怎么查呢？

不要忘了这事一道树剖题，可以利用\(dfs\)序来进行

一颗子树中的\(dfs\)序是连续的

若一个节点\(A\)在一个以\(R\)为根的子树中

其\(dfs\)序大于\(R\)的\(dfs\)序，小于\(R\)的\(dfs\)+\(R\)的子树大小。

所以我们可以枚举\(A\)的儿子，再根据上面这一条定理判断

然后如何使用树剖维护呢

还是根据一棵树中的\(dfs\)序是连续的来做。

如果我们将\(R\)所在的子树的链在线段树中都删去，那么剩下的链就是我们需要查询的区间。 所以我们只需要查询两次就可以了

#include
    
     #include
     
      #include
      
       using std::swap;using std::min;const int maxn=101000;int n,m,r,now_r;struct node{    int p;    int nxt;};node line[maxn<<1];int head[maxn],tail;void add(int a,int b){    line[++tail].p=b;    line[tail].nxt=head[a];    head[a]=tail;}int dep[maxn],id[maxn],f[maxn],top[maxn];int son[maxn],size[maxn],num;int val[maxn],base[maxn];int t[maxn<<2],tag[maxn<<2];void build(int root,int l,int r){    if(l==r)    {        t[root]=base[l];        return ;    }    int mid=(l+r)>>1;    build(root<<1,l,mid);    build(root<<1|1,mid+1,r);    t[root]=min(t[root<<1],t[root<<1|1]);}void push_down(int root,int l,int mid,int r){    if(!tag[root])  return ;    int ls=root<<1,rs=root<<1|1;    tag[ls]=tag[root];    tag[rs]=tag[root];    t[ls]=tag[root];    t[rs]=tag[root];    tag[root]=0;    return ;}void updata(int root,int l,int r,int al,int ar,int val){    if(l>ar||r
       
        =al&&r<=ar)    {        t[root]=val;        tag[root]=val;        return ;    }    int mid=(l+r)>>1;    push_down(root,l,mid,r);    updata(root<<1,l,mid,al,ar,val);    updata(root<<1|1,mid+1,r,al,ar,val);    t[root]=min(t[root<<1],t[root<<1|1]);}int query(int root,int l,int r,int al,int ar){    if(l>ar||r
        
         =al&&r<=ar)    return t[root];    int mid=(l+r)>>1;    push_down(root,l,mid,r);    return  min(query(root<<1,l,mid,al,ar),            query(root<<1|1,mid+1,r,al,ar));}/*----------------------------------------------------线段树*/void dfs1(int now,int fa,int d){    dep[now]=d;    size[now]=1;    f[now]=fa;    int W=-1;    for(int i=head[now];i;i=line[i].nxt)        if(line[i].p!=fa)        {            dfs1(line[i].p,now,d+1);            size[now]+=size[line[i].p];            if(size[line[i].p]>W)                son[now]=line[i].p,W=size[line[i].p];        }}void dfs2(int now,int tf){    top[now]=tf;    id[now]=++num;    base[num]=val[now];    if(!son[now])   return ;    dfs2(son[now],tf);    for(int i=head[now];i;i=line[i].nxt)        if(line[i].p!=f[now]&&line[i].p!=son[now])            dfs2(line[i].p,line[i].p);  }void seg_updata(int a,int b,int c){    while(top[a]!=top[b])    {        if(dep[top[a]]
         
          dep[b]) swap(a,b); updata(1,1,num,id[a],id[b],c); return ;}int lca(int a,int b){ while(top[a]!=top[b]) { if(dep[top[a]]
          
           =id[now_r]&&line[i].p!=f[a]) { S=line[i].p; break; }//使用规律进行查找，这里可以使用倍增加速 return min(query(1,1,num,1,id[S]-1),query(1,1,num,id[S]+size[S],num));//分成两段进行查询}int main(){ scanf("%d%d",&n,&m); int a,b,c; for(int i=1;i