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;
}