题目大意：给定一棵有根树，每个点有一个权值，提供三种操作：

1.将x节点变为根节点

2.将x到y路径上的点的权值全部改为v

3.询问x的子树中点权的最小值

思路：用DFS序剖分，记录每个节点入栈出栈的时间，其之间的区间即为子树。操作2用线段树直接搞，而换根先不管，可用原来的DFS序。询问时分类讨论：记最开始的根为root，换根之后，对于当前的根rtnow和询问子树U而言，

①rtnow==U，询问整棵树

②fa[rtnow]==U，询问除了rtnow所在子树以外的整棵树

③rtnow在U的子树里，且距离大于1，询问除了rtnow的除了其祖先是U的儿子的祖先的子树以外的整棵树

④rtnow不在U的子树里，询问U的子树

代码：

#include<cstdio>
#include<iostream>
#define M 2000000
#define INF 2147483647
using namespace std;

int cnt,dfn,n,m,a[M],to[M],hson[M],next[M],head[M],id[M],size[M],last[M],pos[M],pa[M],deep[M],top[M],cov[M<<2],minv[M<<2];

void ins(int x,int y)
{
     to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;
}

void dfs1(int x)
{
    size[x]=1;
    for (int i=head[x];i;i=next[i])
        if (to[i]!=pa[x])
        {
            pa[to[i]]=x,deep[to[i]]=deep[x]+1;
            dfs1(to[i]),size[x]+=size[to[i]];
            if (size[to[i]]>size[hson[x]]) hson[x]=to[i];
        }
}

void dfs2(int x,int tp)
{
    id[x]=++dfn,pos[dfn]=x,top[x]=tp;
    if (hson[x]) dfs2(hson[x],tp);
    for (int i=head[x];i;i=next[i])
        if (to[i]!=pa[x]&&to[i]!=hson[x]) dfs2(to[i],to[i]);
    last[x]=dfn;
}

void push_down(int k)
{
     if (cov[k])
     {
         cov[k<<1]=cov[k<<1|1]=minv[k<<1]=minv[k<<1|1]=cov[k];
         cov[k]=0;
     }
}

void change(int cur,int L,int R,int l,int r,int val)
{
     if (L==l && R==r) { cov[cur]=minv[cur]=val; return; }
     int mid=L+R>>1; push_down(cur);
     if (r<=mid) change(cur<<1,L,mid,l,r,val);
     else if (l>mid) change(cur<<1|1,mid+1,R,l,r,val);
          else change(cur<<1,L,mid,l,mid,val),change(cur<<1|1,mid+1,R,mid+1,r,val);
     minv[cur]=min(minv[cur<<1],minv[cur<<1|1]);
}

int ask(int cur,int L,int R,int l,int r)
{
    if (L==l && R==r) return minv[cur];
    int mid=L+R>>1; push_down(cur);
    if (r<=mid) return ask(cur<<1,L,mid,l,r);
    if (l>mid) return ask(cur<<1|1,mid+1,R,l,r);
    return min(ask(cur<<1,L,mid,l,mid),ask(cur<<1|1,mid+1,R,mid+1,r));
}

void add(int x,int y,int val)
{
     for (;top[x]!=top[y];x=pa[top[x]])
     {
         if (deep[top[x]]<deep[top[y]]) swap(x,y);
         change(1,1,n,id[top[x]],id[x],val);
     }
     if (deep[x]>deep[y]) swap(x,y);
     change(1,1,n,id[x],id[y],val);
}

int main()
{
    scanf("%d%d",&n,&m);
    int i,x,y,z,op,rt,root=0;
    for (i=1;i<n;i++) scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
    for (i=1;i<=n;i++) scanf("%d",&a[i]);
    scanf("%d",&rt);dfs1(rt),dfs2(rt,rt);
    for (i=1;i<=n;i++) change(1,1,n,id[i],id[i],a[i]);
    while (m--)
    {
          scanf("%d",&op);
          if (op==1) scanf("%d",&root);
          if (op==2) scanf("%d%d%d",&x,&y,&z),add(x,y,z);
          if (op==3)
          {
               scanf("%d",&x);
               if (x==root) printf("%d\n",ask(1,1,n,1,n));
               else if (pa[root]==x) printf("%d\n",min(ask(1,1,n,1,id[root]-1),last[root]==n?INF:ask(1,1,n,last[root]+1,n)));
                    else if (id[root]>=id[x] && id[root]<=last[x])
                         {
                              y=root;
                              while (pa[top[y]]!=x && top[x]!=top[y]) y=pa[top[y]];
                              if (pa[top[y]]!=x) y=pos[id[x]+1];
                              else y=top[y];
                              printf("%d\n",min(ask(1,1,n,1,id[y]-1),last[y]==n?INF:ask(1,1,n,last[y]+1,n)));
                         }
                         else printf("%d\n",ask(1,1,n,id[x],last[x]));
          }
    }
    return 0;
}

题目大意：有一棵树，最先每条边的权值是1，然后给出n+m-1个操作，操作有两种：1.询问一个点到根的路径上的权值和；2.将一条边的权值改为0.

思路：用dfs序将树化为序列，在dfs序中我们会保存节点i进入时间come[i]和出去时间leave[i]，这两个数之间的区间即为其子树。询问实为前缀和，可用树状数组记录。修改只会影响其子树（即区间），其他部分并不会改变（+1-1抵消了）。

代码：

#include<cstdio>
#include<iostream>
#define M 300000 
using namespace std;

int n,m,cnt,dfn,to[M],next[M],head[M],c[M],come[M],leave[M];

int read()
{
    int x=0,y=1;
    char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') y=-1;ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*y;
}

void ins(int x,int y)
{
     to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;
}

void dfs(int x)
{
     come[x]=++dfn;
     for (int i=head[x];i;i=next[i]) dfs(to[i]);
     leave[x]=dfn;
}

void add(int x,int y)
{
     for (;x<=n;x+=x&-x) c[x]+=y;
}

int sum(int x)
{
    int ans=0;
    for (;x;x-=x&-x) ans+=c[x];
    return ans;
}

int main()
{
    int i,j,x,y;
    n=read();
    for (i=1;i<n;i++) x=read(),y=read(),ins(x,y);
    dfs(1);
    m=read();
    for (i=2;i<=n;i++) add(come[i],1),add(leave[i]+1,-1);
    for (i=1;i<n+m;i++)
    {
        char ch=getchar();
        while (ch<'A' || ch>'Z') ch=getchar();
        if (ch=='W') printf("%d\n",sum(come[read()]));
        else x=read(),y=read(),add(come[y],-1),add(leave[y]+1,1);
    }scanf("%d",&n);
    return 0;
}

题目大意：给定一棵n个点的树，每个点有一个权值，m个询问，每次询问树上点x到点y的路径上的第k小数。

思路：dfs后给每个节点一个dfs序，以每个点在他父亲的基础上建立主席树，询问时用(点x+点y-点lca(x,y)-点dad[lca(x,y)])即可得到x到y的链，在上面查询即可。

代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 200009
using namespace std;

int tot=1,dfn,num,cnt,pa[N][18],to[N],next[N],head[N],lc[N*10],rc[N*10],deep[N],sum[N*10],id[N],pos[N],root[N],a[N],b[N];

int read()
{
    int x=0,y=1;char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') y=-1;ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*y;
}

void add(int x,int y)
{
     to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;
}

void dfs(int x)
{
     int i;id[x]=++dfn,pos[dfn]=x;
     for (i=1;i<=16;i++)
         if ((1<<i)<=deep[x]) pa[x][i]=pa[pa[x][i-1]][i-1];
         else break;
     for (i=head[x];i;i=next[i])
         if (pa[x][0]!=to[i])
         {
              deep[to[i]]=deep[x]+1;
              pa[to[i]][0]=x;
              dfs(to[i]);
         }
}

void change(int l,int r,int x,int &cur,int _cur)
{
     cur=++num;
     lc[cur]=lc[_cur];
     rc[cur]=rc[_cur];
     sum[cur]=sum[_cur]+1;
     if (l==r) return;
     int mid=l+r>>1;
     if (x<=b[mid]) change(l,mid,x,lc[cur],lc[_cur]);
     else change(mid+1,r,x,rc[cur],rc[_cur]);
}

int LCA(int x,int y)
{
    if (deep[x]<deep[y]) swap(x,y);
    int i,t=deep[x]-deep[y];
    for (i=0;i<=16;i++)
        if ((1<<i)&t) x=pa[x][i];
    for (i=16;i>=0;i--)
        if (pa[x][i]!=pa[y][i]) x=pa[x][i],y=pa[y][i];
    if (x==y) return x;
    return pa[x][0];
}

int ask(int x,int y,int k)
{
    int a=root[id[x]],b=root[id[y]],c=LCA(x,y),d=pa[c][0],l=1,r=tot;
    c=root[id[c]],d=root[id[d]];
    while (l<r)
    {
          int t=sum[lc[a]]+sum[lc[b]]-sum[lc[c]]-sum[lc[d]],mid=l+r>>1;
          if (t>=k) a=lc[a],b=lc[b],c=lc[c],d=lc[d],r=mid;
          else a=rc[a],b=rc[b],c=rc[c],d=rc[d],l=mid+1,k-=t;
    }
    return l;
}

int main()
{
    int n=read(),m=read(),i,x,y,ans=0,k;
    for (i=1;i<=n;i++) a[i]=read(),b[i]=a[i];
    for (i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x);
    dfs(1),sort(b+1,b+n+1);
    for (i=2;i<=n;i++)
        if (b[tot]!=b[i]) b[++tot]=b[i];
    for(i=1;i<=n;i++) change(1,tot,a[pos[i]],root[i],root[id[pa[pos[i]][0]]]);
    for (i=1;i<=m;i++)
    {
        x=read(),y=read(),k=read(),x^=ans;
        printf("%d",ans=b[ask(x,y,k)]);
        if (i<m) printf("\n");
    }
    return 0;
}