Educational Codeforces Round 25 G. Tree Queries

题目链接
大意：给你一颗树和一些操作(初始所有节点都是白***r> 1:把 $v$v点染成黑***r> 2:找到一个最小节点编号 $y$y,使得 $x$x到某个黑色节点到最短路径上存在节点 $y$y.

思路：我们把第一个变成黑色节点到点 设为根节点，然后求出根节点到所有点的路径上到最小节点编号，设为数组 $f$f，那么如果没有其他黑点的话，那么 $f\left[x\right]$f[x]就是询问点 $x$x的答案了。如果存在别的黑点 $x$x，那么显然 $x$x到根节点的路径上的所有点 ，其他的点都可以到达，更新一下可能到全局最小值 $min$min。 $min,f\left[x\right]$min,f[x]两者取一个最小值即可。
细节见代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
#define fi first
#define se second
#define pb push_back
vector<int> v[N];
int ans[N],fa[N];
void gao(int now, int x, int pre) {
  ans[now] = min(ans[now], x);
  for (auto k : v[now]){
    if (k == pre)
      continue;
    gao(k, min(x, k), now);
  }
}
int main() {
  int n, m, last = 0;
  scanf("%d%d", &n, &m);
  for (int i = 0; i <= n; i++)
    ans[i] = 1e9;
  for (int i = 1; i < n; i++) {
    int s, t;
    scanf("%d%d", &s, &t);
    v[s].pb(t);
    v[t].pb(s);
  }
  int sta=0,qq=1e9;
  for (int i = 1; i <= m; i++) {
    int t, z, x;
    scanf("%d%d", &t, &z);
    x = (z + last) % n + 1;
    if (t == 1) {
      if(!sta)gao(x, x, 0),sta=1;
      else{
        qq=min(qq,ans[x]);
      }
    } else {
      last = min(qq,ans[x]);
      printf("%d\n", last);
    }
  }
  return 0;
}