树链剖分题目选讲

导言

上一节课，我们好好地学习了一波，树链剖分。

光说不练假把式，这是某位大佬的名言。

所以我们来几道题目练练手。。。

说真的，树链剖分的题目，码量惊人。

题目选讲

第一题·[JLOI2014]松鼠的新家

原题链接

题目描述

松鼠的新家是一棵树，前几天刚刚装修了新家，新家有$n$个房间，并且有$n-1$根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在”树“上。

松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去$a_1$，再去$a_2$，......，最后到$a_n$，去参观新家。可是这样会导致维尼重复走很多房间，懒惰的维尼不停地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。

维尼是个馋家伙，立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。

因为松鼠参观指南上的最后一个房间$a_n$是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

输入格式

第一行一个整数$n$，表示房间个数第二行n个整数，依次描述$a_1$-$a_n$

接下来$n-1$行，每行两个整数$x$，$y$，表示标号$x$和$y$的两个房间之间有树枝相连。

输出格式

一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让维尼有糖果吃。

输入输出样例

输入

5
1 4 5 3 2
1 2
2 4
2 3
4 5

输出

1
2
1
2
1

说明/提示

$$ 2<= n <=300000 $$

解题报告

题意理解

就是刚开始，你在一棵树的根节点，$1$号节点，然后你会按照题目给定的顺序，走到$n$个指定地点，而且路上的每一个节点的权值都要+1

简称：

操作一：一条路径上的权值$+1$

操作二：查询一个点的权值

算法解析

我们会着重分析一下，各大操作。

1. 一条路径上区间修改

对于这个操作而言，基本上就是树链剖分的模板操作了。

1. 查询一个点的权值

这个操作，也很好理解，我们就不细说了。

我们似乎发现这道题目真的很水啊。

然后还有更水的做法。

最近公共祖先+树上差分

所以其实这道题目，完全不需要高大上的树链剖分。

你感觉自己被骗了，没错，这种情况就是数据结构学傻的感觉。

实际上这道题目，我们完全可以通过之前讲解的基础算法处理。

对于一条路径上的权值$+1$，而且是点权。

我们自然会想到以下方法。

date[x]++;
date[y]++;
date[Lca(x,y)]--;
date[fa[Lca(x,y)]]--;

于是我们就解决了这道题目。

实际上，这道题目只是一个开胃小菜，因为讲课人担心，刚开始太难了，会让你无法承受。。。

于是这道题目不是树链剖分。

代码解析

#include <bits/stdc++.h>
using namespace std;
const int N=6e5+20;
int fa[N][32],a[N],deep[N],cnt[N],lg[N],date[N];
int tot,head[N],edge[N],Next[N],n;
inline void add_edge(int a,int b)
{
    edge[++tot]=b;
    Next[tot]=head[a];
    head[a]=tot;
}
int dfs(int x,int s)
{
    deep[x]=deep[s]+1;
    fa[x][0]=s;
    for(int i=1; fa[x][i-1]; i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=head[x]; i; i=Next[i])
        if(edge[i]!=s)
            dfs(edge[i],x);
}
inline int Lca(int x,int y)
{
    if(deep[x]<deep[y])
        swap(x,y);
    for(int i=20; i>=0; i--)
        if(deep[x]-(1<<i)>=deep[y])
            x=fa[x][i];
    if(x==y)
        return x;
    for(int i=20; i>=0; i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
void Tree(int a,int b)
{
    date[a]++;
    date[b]++;
    int c=Lca(a,b);
    date[c]--;
    date[fa[c][0]]--;
}
void Query(int x)
{
    for(int i=head[x]; i; i=Next[i])
    {
        int y=edge[i];
        if (y==fa[x][0])
            continue;
        Query(y);
        date[x]+=date[y];
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    for(int i=1; i<n; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add_edge(a,b);
        add_edge(b,a);
    }
    dfs(1,0);
    for(int i=1; i<n; i++)
        Tree(a[i],a[i+1]);
    Query(1);
    date[a[1]]++;
    for(int i=1; i<=n; i++)
        printf("%d\n",date[i]-1);
    return 0;
}

第二题·[SHOI2012]魔法树

题目描述

$Harry Potter$ 新学了一种魔法：可以让改变树上的果子个数。满心欢喜的他找到了一个巨大的果树，来试验他的新法术。

这棵果树共有$N$个节点，其中节点$0$是根节点，每个节点$u$的父亲记为$fa[u]$，保证有$fa[u] < u$。初始时，这棵果树上的果子都被 Dumbledore 用魔法清除掉了，所以这个果树的每个节点上都没有果子（即$0$个果子）。

不幸的是，Harry 的法术学得不到位，只能对树上一段路径的节点上的果子个数统一增加一定的数量。也就是说，Harry 的魔法可以这样描述：

$Add$ u v d

表示将点u和v之间的路径上的所有节点的果子个数都加上d。

接下来，为了方便检验 Harry 的魔法是否成功，你需要告诉他在释放魔法的过程中的一些有关果树的信息：

$Query$ u

表示当前果树中，以点u为根的子树中，总共有多少个果子？

输入格式

第一行一个正整数N ($1 \le N ≤ 100000$)，表示果树的节点总数，节点以$0,1,…,N − 1$标号，0一定代表根节点。

接下来$N − 1$行，每行两个整数a,b ($0 \le a < b < N$)，表示a是b的父亲。

接下来是一个正整数Q(1 \le Q \le 100000)，表示共有Q次操作。

后面跟着$Q$行，每行是以下两种中的一种：

1. A u v d，表示将$u$到$v$的路径上的所有节点的果子数加上$d$；$0 \le u,v <N,0 < d < 100000$
2. Q u，表示询问以$u$为根的子树中的总果子数，注意是包括$u$本身的。

输出格式

对于所有的$Query$操作，依次输出询问的答案，每行一个。答案可能会超过$2^{32}$ ，但不会超过${10}^{15}$ 。

输入输出样例

输入

4
0 1
1 2
2 3
4
A 1 3 1
Q 0
Q 1
Q 2

输出

3
3
2

解题报告

题意理解

这道题目的一大特殊就是。
$$ 点权=>边权 $$
然后多了两个操作。

1. 将一条路径上的边，统统加上一个权值
2. 统计一颗子树的总边权。

算法解析

对于操作而言，其实我们在上一次课已经讲解过了，而本次课的重难点，就是树链剖分的拓展。

我们来分析以下，之前讲解树上差分的时候，我们是怎么理解点权变成边权的。

我们理解一个点。

1. 一个点有很多个儿子
2. 一个点只有一个父亲

因此这么说的话，我们将会发现，一条边可以这样被确定。

假如说有一条边。
$$ x=>y \\\\ x是父亲，y是儿子 $$
那么这样的话，我们不妨用儿子节点$y$来表示这条边。

因此我们得出了非常重要的结论。

1. 儿子节点，表示指向父亲的边。

2. 根节点不做处理。

好的那么这道题目，也就迎刃而解了。

讲题人相信，区区的模板操作，是难不倒你们的。

代码解析

#include <bits/stdc++.h>
using namespace std;
#define read(x) scanf("%d",&x)
const int N=1e5+20;//节点总数
int n,q,a,b,v;
int deep[N],wson[N],size[N];//深度;重儿子编号;子树大小
int fa[N],top[N],dfn[N],cnt;//记录父亲节点;链头;DFS序;新编号，就是DFS序
int head[N],edge[N],Next[N],tot;//链头；出边节点；链表；边总数
long long sum[N<<2],Lazy[N<<2];//线段树四倍空间
struct Line_tree//线段树
{
#define mid  (l+r>>1)//中间点
#define Lson rt<<1,l,mid//左儿子
#define Rson rt<<1 | 1,mid+1,r//右儿子
#define Len  (r-l+1)//区间长度
    void Push_up(int rt)
    {
        sum[rt]=sum[rt<<1]+sum[rt<<1 | 1];//父亲节点=左儿子+右儿子节点
        return ;
    }
    void Push_down(int rt,int l,int r)
    {
        if (!Lazy[rt])//没有标记下传
            return ;
        Lazy[rt<<1]+=Lazy[rt];//下传标记给左儿子
        Lazy[rt<<1 | 1]+=Lazy[rt];//下传标记给右儿子
        sum[rt<<1]+=Lazy[rt]*(Len-(Len>>1));//懒惰标记的值叠加
        sum[rt<<1 | 1]+=Lazy[rt]*(Len>>1);//懒惰标记的值叠加
        Lazy[rt]=0;//直接清空
    }
    void build(int rt,int l,int r)//建树
    {
        if (l==r)
        {
            sum[rt]=Lazy[rt]=0;//初始都为0
            return ;
        }
        build(Lson);//左儿子
        build(Rson);//右儿子
        Push_up(rt);
    }
    void Update(int rt,int l,int r,int L,int R,int v)//当前区间[l,r],目前区间[L,R],全部加上v
    {
        if (L<=l && r<=R)//当前区间在目标区间内
        {
            Lazy[rt]+=v;//这个区间都要增加v
            sum[rt]+=v*Len;//区间增加
            return ;
        }
        Push_down(rt,l,r);//下传标记
        if (L<=mid)//左儿子
            Update(Lson,L,R,v);
        if (R>mid)//右儿子
            Update(Rson,L,R,v);
        Push_up(rt);
    }
    long long Query(int rt,int l,int r,int L,int R)//当前区间[l,r],查询目标区间[L,R]
    {
        long long ans=0;
        if (L<=l && r<=R)//目标区间包含当前区间
            return sum[rt];
        Push_down(rt,l,r);//标记下传
        if (L<=mid)
            ans+=Query(Lson,L,R);//左儿子
        if (R>mid)
            ans+=Query(Rson,L,R);//右儿子
        return ans;
    }
} t1;
struct Tree_Chain//树链剖分
{
    inline void add_edge(int a,int b)//加边
    {
        edge[++tot]=b;//出边节点
        Next[tot]=head[a];//连接
        head[a]=tot;//编号
    }
    void dfs1(int x,int father)
    {
        size[x]=1;//初始时候，子树大小为1
        for(int i=head[x]; i; i=Next[i])//遍历所有儿子节点
        {
            int y=edge[i];//出边，也就是儿子节点
            if (y==father)//不可以返回到父亲节点
                continue;
            deep[y]=deep[x]+1;//儿子深度是父亲深度+1
            fa[y]=x;//儿子节点是父亲节点
            dfs1(y,x);//儿子节点；儿子节点的父亲是自己
            size[x]+=size[y];//累加儿子节点的贡献的大小
            if (size[y]>size[wson[x]])//这个儿子节点比重儿子节点数量还多，那么更新
                wson[x]=y;//更新重儿子编号
        }
    }
    void dfs2(int x,int tp)//节点；节点的链头
    {
        dfn[x]=++cnt;//当前节点记录DFS序
        top[x]=tp;//记录
        if (wson[x])//优先访问重儿子
            dfs2(wson[x],tp);//重儿子编号；重儿子的链头，肯定和父亲是一样的
        for(int i=head[x]; i; i=Next[i])//遍历所有的轻儿子
        {
            int y=edge[i];
            if (y==fa[x] || y==wson[x])//不可以是父亲节点，也不可以是重儿子
                continue;
            dfs2(y,y);//轻儿子，轻链，重链的开头都是轻儿子
        }
    }
    void Update_sum(int a,int b,int v)//修改a到b这条链，统统加上v
    {
        while(top[a]!=top[b])//此时A，B不在同一条重链
        {
            if (deep[top[a]]<deep[top[b]])//我们这里默认a节点是深度在下面的链
                swap(a,b);
            t1.Update(1,1,n,dfn[top[a]],dfn[a],v);//加上这条链上的值
            a=fa[top[a]];//a可以跳到链头上面
        }
        if (dfn[a]<dfn[b])//还是默认
            swap(a,b);
        t1.Update(1,1,n,dfn[b],dfn[a],v);
    }
    long long Query_sum(int x)//查询子树的和
    {
        return t1.Query(1,1,n,dfn[x],dfn[x]+size[x]-1);//统计子树和
    }
} t2;
inline void init()
{
    read(n);
    for(int i=1; i<n; i++)
    {
        read(a),read(b);
        a++,b++;//编号自动+1
        t2.add_edge(a,b);
    }
    t2.dfs1(1,0);
    t2.dfs2(1,1);
    t1.build(1,1,n);
    read(q);
    while(q--)
    {
        char s[3];
        scanf("%s",s);
        if (s[0]=='A')
        {
            read(a),read(b),read(v);
            a++,b++;//编号自动+1
            t2.Update_sum(a,b,v);//区间修改
        }
        else
        {
            read(a);
            a++;//编号自动+1
            long long ans=t2.Query_sum(a);
            printf("%lld\n",ans);
        }
    }
}
int main()
{
    init();
    return 0;
}

第三题·月下毛景树

题目描述

毛毛虫经过及时的变形，最终逃过的一劫，离开了菜妈的菜园。 毛毛虫经过千山万水，历尽千辛万苦，最后来到了小小的绍兴一中的校园里。

爬啊爬~爬啊爬毛毛虫爬到了一颗小小的“毛景树”下面，发现树上长着他最爱吃的毛毛果~ “毛景树”上有N个节点和N-1条树枝，但节点上是没有毛毛果的，毛毛果都是长在树枝上的。但是这棵“毛景树”有着神奇的魔力，他能改变树枝上毛毛果的个数：

• Change k w：将第k条树枝上毛毛果的个数改变为w个。
• Cover u v w：将节点u与节点v之间的树枝上毛毛果的个数都改变为w个。
• Add u v w：将节点u与节点v之间的树枝上毛毛果的个数都增加w个。 由于毛毛虫很贪，于是他会有如下询问：
• Max u v：询问节点u与节点v之间树枝上毛毛果个数最多有多少个。

输入格式

第一行一个正整数N。

接下来N-1行，每行三个正整数Ui，Vi和Wi，第i+1行描述第i条树枝。表示第i条树枝连接节点Ui和节点Vi，树枝上有Wi个毛毛果。 接下来是操作和询问，以“Stop”结束。

输出格式

对于毛毛虫的每个询问操作，输出一个答案。

输入输出样例

输入 #1

4
1 2 8
1 3 7
3 4 9
Max 2 4
Cover 2 4 5
Add 1 4 10
Change 1 16
Max 2 4
Stop

输出 #1

9
16

说明/提示

$1 \le N \le 100,000$，操作+询问数目不超过$100,000$。

保证在任意时刻，所有树枝上毛毛果的个数都不会超过$10^9$个。

解题报告

题意理解

这道题目，和上一道题目一样，都是有几大操作&边权处理。

我们来分析这道题目的操作们。

1. 边权
2. 单边权值修改
3. 路径权值修改
4. 路径权值增加
5. 路径最大值

分析完这道题目的操作了，就要看如果解析这道题目了。

算法解析

如果说把修改，增加这两大操作分别处理，相信各位精通线段树，区间修改&懒惰标记大佬们，肯定处理起来游刃有余。

再加上刚才，我们讲解了边权的转化，相信这道题目思维难度来说不难。

但是关键就是，区间修改&区间增加这两个操作放在了一起。

请问懒惰标记如何处理

我们知道，对于区间修改而言，懒惰标记是这样的。
$$ Lazy[rt]=val $$
但是，对于区间增加，懒惰标记是这样的。
$$ Lazy[rt]+=val $$
表面看起来，这个懒惰标记并没有什么。

但是假如说，先来一次区间增加，再来一次区间修改。

那么我们发现.
$$ Lazy[rt]=val $$
因为此时，我们的懒惰标记，显然要优先后来的区间修改。

那么假如说，顺序不是这样的，是先来区间修改，再来区间增加。
$$ Lazy[rt]=val1 \\\\ Lazy[rt]+=val2 $$
这样看，我们发现这两个操作之间，存在懒惰标记更新的冲突。

下传标记，到底是修改呢？还是更新呢？

逻辑关系处理，该怎么办呢？

不妨使用，双懒惰标记

既然这样的话，我们就不难处理这道题目了。

对于标记下传而言

1. 假如说区间修改了，那么区间增加的懒惰标记清空。
2. 假如说区间增加了，有区间修改，优先处理区间修改，然后再区间增加。

既然如此，这道题目我们就巧妙解决了。

代码解析

#include <bits/stdc++.h>
using namespace std;
#define read(x) scanf("%d",&x)
const int N=2e5+20;
int n,a[N],edge[N<<1],ver[N<<1],Next[N<<1],head[N],tot;
int deep[N],size[N],wson[N],fa[N],top[N],pre[N],dfn[N],cnt;
struct Line_tree
{
    #define Lson rt<<1,l,mid
    #define Rson rt<<1 | 1,mid+1,r
    #define mid  (l+r>>1)
    #define ls   rt<<1
    #define rs   rt<<1 | 1
    int Max[N<<2],Lazy[N<<2],tag[N<<2];
    void Push_up(int rt)
    {
        Max[rt]=max(Max[ls],Max[rs]);
    }
    void Push_down(int rt)
    {
        if(tag[rt]>=0)
        {
            Lazy[ls]=Lazy[rs]=0;
            Max[ls]=Max[rs]=tag[ls]=tag[rs]=tag[rt];
            tag[rt]=-1;
        }
        if(Lazy[rt])
        {
            Lazy[ls]+=Lazy[rt];
            Lazy[rs]+=Lazy[rt];
            Max[ls]+=Lazy[rt];
            Max[rs]+=Lazy[rt];
            Lazy[rt]=0;
        }
    }
    void build(int rt,int l,int r)
    {
        tag[rt]=-1;
        if (l==r)
        {
            Max[rt]=pre[l];
            return ;
        }
        build(Lson);
        build(Rson);
        Push_up(rt);
    }
    void Update(int rt,int l,int r,int L,int R,int v)
    {
        if (L<=l && r<=R)
        {
            Max[rt]=tag[rt]=v;
            Lazy[rt]=0;
            return ;
        }
        Push_down(rt);
        if (L<=mid)
            Update(Lson,L,R,v);
        if (R>mid)
            Update(Rson,L,R,v);
        Push_up(rt);
    }
    void Add(int rt,int l,int r,int L,int R,int v)
    {
        if (L<=l && r<=R)
        {
            Max[rt]+=v;
            Lazy[rt]+=v;
            return ;
        }
        Push_down(rt);
        if (L<=mid)
            Add(Lson,L,R,v);
        if (R>mid)
            Add(Rson,L,R,v);
        Push_up(rt);
    }
    int Query_max(int rt,int l,int r,int L,int R)
    {
        if(L<=l && r<=R)
            return Max[rt];
        int ans=0;
        Push_down(rt);
        if(L<=mid)
            ans=max(ans,Query_max(Lson,L,R));
        if(R>mid)
            ans=max(ans,Query_max(Rson,L,R));
        return ans;
    }
} t1;
struct Chain_tree
{
    void dfs1(int x,int s)
    {
        size[x]=1;
        for(int i=head[x]; i; i=Next[i])
        {
            int y=edge[i];
            if (y==s)
                continue;
            a[y]=ver[i];
            fa[y]=x;
            deep[y]=deep[x]+1;
            dfs1(y,x);
            size[x]+=size[y];
            if (size[wson[x]]<size[y])
                wson[x]=y;
        }
    }
    void dfs2(int x,int tp)
    {
        dfn[x]=++cnt;
        pre[cnt]=a[x];
        top[x]=tp;
        if (wson[x])
            dfs2(wson[x],tp);
        for(int i=head[x]; i; i=Next[i])
        {
            int y=edge[i];
            if (y==wson[x] || y==fa[x])
                continue;
            dfs2(y,y);
        }
    }
    int Query_max(int a,int b)
    {
        int ans=0;
        while(top[a]!=top[b])
        {
            if (deep[top[a]]<deep[top[b]])
                swap(a,b);
            ans=max(ans,t1.Query_max(1,1,n,dfn[top[a]],dfn[a]));
            a=fa[top[a]];
        }
        if(dfn[a]>dfn[b])
            swap(a,b);
        ans=max(ans,t1.Query_max(1,1,n,dfn[a]+1,dfn[b]));
        return ans;
    }
    void Update(int a,int b,int w,int s)
    {
        while(top[a]!=top[b])
        {
            if (deep[top[a]]<deep[top[b]])
                swap(a,b);
            if (s==1)
                t1.Update(1,1,n,dfn[top[a]],dfn[a],w);
            else
                t1.Add(1,1,n,dfn[top[a]],dfn[a],w);
            a=fa[top[a]];
        }
        if(dfn[a]>dfn[b])
            swap(a,b);
        if (s==1)
            t1.Update(1,1,n,dfn[a]+1,dfn[b],w);
        else
            t1.Add(1,1,n,dfn[a]+1,dfn[b],w);
    }
} t2;
void add_edge(int a,int b,int c)
{
    edge[++tot]=b;
    ver[tot]=c;
    Next[tot]=head[a];
    head[a]=tot;
}
int main()
{
    read(n);
    for(int i=1; i<n; i++)
    {
        int a,b,c;
        read(a),read(b),read(c);
        add_edge(a,b,c);
        add_edge(b,a,c);
    }
    t2.dfs1(1,0),t2.dfs2(1,1),t1.build(1,1,n);
    while(1)
    {
        char s[12];
        scanf("%s",&s);
        if (s[0]=='C' && s[1]=='h')
        {
            int a,b;
            read(a),read(b);
            a=deep[edge[a*2-1]]<deep[edge[a*2]]?edge[a*2]:edge[a*2-1];
            t1.Update(1,1,n,dfn[a],dfn[a],b);
        }
        if (s[0]=='C' && s[1]=='o')
        {
            int a,b,c;
            read(a),read(b),read(c);
            t2.Update(a,b,c,1);
        }
        if (s[0]=='A')
        {
            int a,b,c;
            read(a),read(b),read(c);
            t2.Update(a,b,c,2);
        }
        if (s[0]=='M')
        {
            int a,b;
            read(a),read(b);
            printf("%d\n",t2.Query_max(a,b));
        }
        if (s[0]=='S')
            break;
    }
    return 0;
}

第四题·Qtree3

题目描述

给出N个点的一棵树（N-1条边），节点有白有黑，初始全为白

有两种操作：

0 i : 改变某点的颜色（原来是黑的变白，原来是白的变黑）

1 v : 询问1到v的路径上的第一个黑点，若无，输出-1

输入格式

第一行 N，Q，表示N个点和Q个操作

第二行到第N行N-1条无向边

再之后Q行，每行一个操作”0 i” 或者”1 v” (1 ≤ i, v ≤ N).

输出格式

对每个1 v操作输出结果

输入输出样例

输入 #1

9 8
1 2
1 3
2 4
2 9
5 9
7 9
8 9
6 8
1 3
0 8
1 6
1 7
0 2
1 9
0 2
1 9 

输出 #1

-1
8
-1
2
-1

说明/提示

For 1/3 of the test cases, $N=5000, Q=400000$.

For 1/3 of the test cases, $N=10000, Q=300000$.

For 1/3 of the test cases, $N=100000, Q=100000$.

解题报告

题意理解

这道题目，看上去似乎无论哪一个操作，我们都觉得怪怪的，似乎都木有学过。

黑白染色操作，是什么啊？

你问我，我也不知道。。。

1. 异或染色
2. 查询深度最浅的黑点所在位置

操作总结完毕了，那么接下来就是传说中的难题了。

实际上，这道题目最简单，最好写，最好打。

算法解析

这道题目只运用到了树链剖分的思想。

我们发现，黑点的出现，就像插入操作一样。

然后黑点变成白点，就像删除操作一样。

查询操作，就是查询最小值操作一样。

我们完全可以用平衡树维护每一条树链。

天啦噜，平衡树不会打死吗？

你要知道，C++ STL有一个叫做set集合的东西，他内部封装了红黑树啊！

于是这道题目，成为了最好写的题目。

代码解析

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+20;
#define read(x) scanf("%d",&x)
int head[N],edge[N<<2],Next[N<<2],ver[N<<2],tot,n,q,a[N];
int size[N],deep[N],fa[N],wson[N],dfn[N],pre[N],top[N],cnt;
set<int> p[N];
inline void add_edge(int a,int b)
{
    edge[++tot]=b;
    Next[tot]=head[a];
    head[a]=tot;
}
void dfs1(int x,int s)
{
    size[x]=1;
    for(int i=head[x]; i ; i=Next[i])
    {
        int y=edge[i];
        if (y==s)
            continue;
        deep[y]=deep[x]+1;
        fa[y]=x;
        dfs1(y,x);
        size[x]+=size[y];
        if (size[wson[x]]<size[y])
            wson[x]=y;
    }
}
void dfs2(int x,int tp)
{
    dfn[++cnt]=x;
    pre[x]=cnt;
    top[x]=tp;
    if (wson[x])
        dfs2(wson[x],tp);
    for(int i=head[x]; i; i=Next[i])
    {
        int y=edge[i];
        if (y==fa[x] || y==wson[x])
            continue;
        dfs2(y,y);
    }
}
inline void init()
{
    read(n),read(q);
    for(int i=1; i<n; i++)
    {
        int a,b;
        read(a),read(b);
        add_edge(a,b);
        add_edge(b,a);
    }
    dfs1(1,0);
    dfs2(1,1);
    while(q--)
    {
        int opt,x;
        read(opt),read(x);
        if (!opt)
        {
            a[x]^=1;
            if(a[x])
                p[top[x]].insert(pre[x]);
            else
                p[top[x]].erase(pre[x]);
        }
        else
        {
            int ans=-1;
            while(x)
            {
                int k=*p[top[x]].begin();
                if(p[top[x]].size() && deep[dfn[k]]<=deep[x])
                    ans=dfn[k];
                x=fa[top[x]];
            }
            printf("%d\n",ans);
        }
    }
}
int main()
{
    init();
    return 0;
}