CF825G Tree Queries 题解

题意：

题目描述：

给定一棵包含 $n$ 个节点的树（从 1 到 $n$ 编号），初始所有节点都是白色的。

你需要处理以下两种类型的 $n$ 个询问:

1 x 将节点 $x$ 的颜色变成黑色。保证第一个询问为这种类型。

2 x 对于顶点 $x$ ，找到最小的下标 $y$ ，使得顶点 $y$ 在一条从 $x$ 到某个黑点的简单路径上。

对于每个第 $2$ 种类型的询问，输出对应的下标 $y$ 。注意询问是强制在线的。

输入格式：

第一行包含两个正整数 $n, q(3 \leq n, q \leq 10^6)$ 。

接下来的 $n-1$ 行，每行包含两个正整数 $x_i, y_i\left(1 \leq x_i<y_i \leq n\right)$，表示有一条边连接顶点 $x_i$ 和顶点 $y_i$ 。

保证给出的图是一棵树。

保证第一个询问为类型 $1\left(t_1=1\right)$ ，且至少有一个询问为类型 $2$。

输出格式：

对于每个类型 $2$ 的询问, 输出一行一个整数, 表示最小的 $y$ 值。

第一眼以为是数据结构题。~~然后什么树剖啊线段树维护括号序啊都冒出来了~~

实际上就是个小 trick 题。注意到在第一个点染了黑色之后，任何结点都与这个黑点连通。

而一条路径的子段肯定不如它本身，所以我们在第一次操作之后就把这个点提作根。

然后从根扫一遍，维护一个 $f_u$ 表示 $u$ 到根的路径上的最小编号。

再用一个变量 $\mathtt{res}$ 表示当前的答案。

那么操作一就变成了 $\mathtt{res} \downarrow f_x$ ，因为此时 $x$ 到 $\mathtt{rt}$ 的路径上每一个点无论如何都可以产生贡献。

操作二直接输出 $\min\{\mathtt{res},f_x\}$ 即可，注意这里不改变 $\mathtt{res}$ 的值。

时间复杂度 $\mathcal{O}(n + q)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6+15))

int n,Q,_,rt,pos=1,f[N],head[N];
struct Edge{ int u,v,next; }e[N * 2];
void addEdge(int u,int v)
{ e[++pos] = {u,v,head[u]}; head[u] = pos; }
void dfs(int u,int fa)
{
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v; if(v == fa) continue;
        down(f[v] = f[u], v); dfs(v,u);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> Q;
    for(int i=1,u,v; i<n; i++)
    {
        cin >> u >> v;
        addEdge(u,v); addEdge(v,u);
    }
    cin >> _ >> rt; int res = (rt = rt % n + 1);
    f[rt] = rt; dfs(rt,0);
    for(int last=0,op,v; --Q; )
    {
        cin >> op >> v; v = (v + last) % n + 1;
        if(op == 1) down(res, f[v]);
        else cout << (last = min(res, f[v])) << '\n';
    }
    return 0;
}