AC日记——825G - Tree Queries

水深无声 2021-12-18 06:07 306阅读 0赞

825G - Tree Queries

思路:

  神题,路径拆成半链;

代码:

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  6. #define maxn 1000005
  7. #define INF 0x3f3f3f3f
  8. int n,m,val[maxn],head[maxn],E[maxn<<1],V[maxn<<1];
  9. int cnt,root,last,ans=INF;
  10. inline void in(int &now)
  11. {
  12. char Cget=getchar();now=0;
  13. while(Cget>'9'||Cget<'0') Cget=getchar();
  14. while(Cget>='0'&&Cget<='9')
  15. {
  16. now=now*10+Cget-'0';
  17. Cget=getchar();
  18. }
  19. }
  20. void dfs(int now,int fa,int Min)
  21. {
  22. val[now]=min(now,Min),Min=min(now,Min);
  23. for(int i=head[now];i;i=E[i])
  24. {
  25. if(fa==V[i]) continue;
  26. dfs(V[i],now,Min);
  27. }
  28. }
  29. int main()
  30. {
  31. //freopen("data.txt","r",stdin);
  32. in(n),in(m);int u,v;
  33. for(int i=1;i<n;i++)
  34. {
  35. in(u),in(v);
  36. E[++cnt]=head[u],V[cnt]=v,head[u]=cnt;
  37. E[++cnt]=head[v],V[cnt]=u,head[v]=cnt;
  38. }
  39. in(root),in(root),root=root%n+1,dfs(root,0,INF);
  40. for(int i=1;i<m;i++)
  41. {
  42. in(u),in(v);
  43. v=(last+v)%n+1;
  44. if(u==1) ans=min(val[v],ans);
  45. if(u==2) last=min(ans,val[v]),printf("%d\n",last);
  46. }
  47. return 0;
  48. }

转载于:https://www.cnblogs.com/IUUUUUUUskyyy/p/7223511.html

发表评论

表情:
评论列表 (有 0 条评论,306人围观)

还没有评论,来说两句吧...

相关阅读