Educational Codeforces Round 25 G. Tree Queries

题目链接：Educational Codeforces Round 25 G. Tree Queries

题意：

给你一棵树，一开始所有的点全是黑色，有两种操作。

1 x 将x这个点变为黑色，保证第一个操作是这个。

2 x 询问x到任意黑色的点的简单路径上的最小节点编号。

题解：

首先将一个变为黑色的点当成树根，然后dfs一下，预处理出所有点的答案。

然后开一个变量记录一下当前变黑的点的答案cur=min(cur,dp[x])。

每次询问的时候答案就是min(cur,dp[x])。

如果觉得很神奇，自己模拟一遍就知道了。

#include<bits/stdc++.h>
#define F(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;

const int N=1e6+7;
vector<int>g[N];
int n,m,x,y,dp[N];

void dfs(int x,int f)
{
    dp[x]=min(x,dp[f]);
    for(int &it:g[x])if(it!=f)dfs(it,x);
}

int main(){
    scanf("%d%d",&n,&m);
    F(i,2,n)
    {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dp[0]=N;
    int last=0,cur=N;
    F(i,1,m)
    {
        scanf("%d%d",&x,&y);
        y=(y+last)%n+1;
        if(x==1)
        {
            if(i==1)dfs(y,0);
            cur=min(cur,dp[y]);
        }else printf("%d
",last=min(cur,dp[y]));
    }
    return 0;
}