题目链接：Educational Codeforces Round 25 G. Tree Queries
题意：
给你一棵树，一开始所有的点全是黑色，有两种操作。
1 x 将x这个点变为黑色，保证第一个操作是这个。
2 x 询问x到任意黑色的点的简单路径上的最小节点编号。
题解：
首先将一个变为黑色的点当成树根，然后dfs一下，预处理出所有点的答案。
然后开一个变量记录一下当前变黑的点的答案cur=min(cur,dp[x])。
每次询问的时候答案就是min(cur,dp[x])。
如果觉得很神奇，自己模拟一遍就知道了。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=(a);i<=(b);++i) 3 using namespace std; 4 5 const int N=1e6+7; 6 vector<int>g[N]; 7 int n,m,x,y,dp[N]; 8 9 void dfs(int x,int f)10 {11dp[x]=min(x,dp[f]);12for(int &it:g[x])if(it!=f)dfs(it,x);13 }14 15 int main(){16scanf("%d%d",&n,&m);17F(i,2,n)18{19 scanf("%d%d",&x,&y);20 g[x].push_back(y);21 g[y].push_back(x);22}23dp[0]=N;24int last=0,cur=N;25F(i,1,m)26{27 scanf("%d%d",&x,&y);28 y=(y+last)%n+1;29 if(x==1)30 {31 if(i==1)dfs(y,0);32 cur=min(cur,dp[y]);33 }else printf("%d\n",last=min(cur,dp[y]));34}35return 0;36 }
View Code
