AC日记——825G - Tree Queries
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<<1],V[maxn<<1];
int cnt,root,last,ans=INF;
inline void in(int &now)
{
char Cget=getchar();now=0;
while(Cget>'9'||Cget<'0') Cget=getchar();
while(Cget>='0'&&Cget<='9')
{
now=now*10+Cget-'0';
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=1;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+1,dfs(root,0,INF);
for(int i=1;i<m;i++)
{
in(u),in(v);
v=(last+v)%n+1;
if(u==1) ans=min(val[v],ans);
if(u==2) last=min(ans,val[v]),printf("%d\n",last);
}
return 0;
}
转载于//www.cnblogs.com/IUUUUUUUskyyy/p/7223511.html
还没有评论,来说两句吧...