825G - Tree Queries
思路：
神题，路径拆成半链；
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 1000005
#define INF 0x3f3f3f3f
int n,m,val[maxn],head[maxn],E[maxn<<],V[maxn<<];
int cnt,root,last,ans=INF;
inline void in(int &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'') Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
}
void dfs(int now,int fa,int Min)
{
val[now]=min(now,Min),Min=min(now,Min);
for(int i=head[now];i;i=E[i])
{
if(fa==V[i]) continue;
dfs(V[i],now,Min);
}
}
int main()
{
//freopen("data.txt","r",stdin);
in(n),in(m);int u,v;
for(int i=;i<n;i++)
{
in(u),in(v);
E[++cnt]=head[u],V[cnt]=v,head[u]=cnt;
E[++cnt]=head[v],V[cnt]=u,head[v]=cnt;
}
in(root),in(root),root=root%n+,dfs(root,,INF);
for(int i=;i<m;i++)
{
in(u),in(v);
v=(last+v)%n+;
if(u==) ans=min(val[v],ans);
if(u==) last=min(ans,val[v]),printf("%d\n",last);
}
return ;
}
