CF825G Tree Queries
2024-08-23 04:02:49
【题意】
一棵树有n个节点,初始均为白色,有两种操作:
1. 1 x 代表把结点 x 设置为黑色
2. 2 x 代表查询 x 到树上任意一个黑色结点的简单路径上的编号最小的结点的编号
输入 t 和 z ,其中 t 表示操作类型, x=(last+z)mod n+1,last代表上一次询问答案,初始为 0 ,保证第一个操作为 1
【数据范围】
n,q<=1e6.
【题解】
发现第一个操作保证是1,则可以以第一个染黑的点为根,则每个点到它路径上最小值dis[i]可以预处理出。
发现一个点到所有黑点路径中编号最小的为每个黑点与这个点到根上的编号最小值。
代码如下:
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+;
int n,q,last[N],dis[N],size,last1,opt,xx,zx;
struct pigu
{
int dao,ne;
}a[N<<];
inline void lingjiebiao(int x,int y)
{
a[++size].dao=y;
a[size].ne=last[x];
last[x]=size;
}
inline void dfs(int now,int fa)
{
dis[now]=min(dis[now],now);
for(int i=last[now];i;i=a[i].ne)
{
if(a[i].dao==fa) continue;
dis[a[i].dao]=dis[now];
dfs(a[i].dao,now);
}
}
inline int read()
{
char c=getchar();
int x=;
while(!isdigit(c)) c=getchar();
while(isdigit(c)) {x=(x<<)+(x<<)+c-'';c=getchar();}
return x;
}
int main()
{
memset(dis,0x3f,sizeof(dis));
n=read();q=read();
for(int i=,x,y;i<=n-;i++)
{
x=read();y=read();
lingjiebiao(x,y);
lingjiebiao(y,x);
}
opt=read();xx=read();
int rt=xx%n+;
dfs(rt,);
zx=dis[rt];
for(int i=;i<=q-;i++)
{
opt=read();xx=read();
xx=(last1+xx)%n+;
if(opt==)
{
zx=min(zx,dis[xx]);
}
else
{
cout<<min(zx,dis[xx])<<"\n";
xx=min(zx,dis[xx]);
last1=xx;
}
}
}
最新文章
- 判断IEnumerable<;T>;集合中是否包含有T对象
- HYSBZ 2002 分块
- DataRead 和DataSet区别
- 未在本地计算机上注册";microsoft.ACE.oledb.12.0";提供程序解决办法
- C语言 ---- 循环分支 iOS学习-----细碎知识点总结
- Java 集合系列 14 hashCode
- 配置Windows 2008 R2 64位 Odoo 8.0/9.0 源码开发调试环境
- git安装教程
- jQuery 效果方法
- hadoop单机安装
- 如何在sqlserver建立新用户并关联相应的数据库
- hiberation4 获取session
- JDK解压版制作
- Elasticsearch简介和安装对比
- mac host文件配置
- boost::bind 介绍
- Shell-9--条件测试
- Intel SP处理机以及AMD处理器的一些对比资料
- 《UnityShader入门精要》学习笔记之渲染流水线
- 【BZOJ 4569】 4569: [Scoi2016]萌萌哒 (倍增+并查集)
热门文章
- error LNK2001: unresolved external symbol __imp___rt_sdiv
- Fragment学习(二): 管理Fragment和Fragment通讯
- hdu 1556 Color the ball(区间更新,单点求值)
- laravel中将session由文件保存改为数据库保存
- Python--day63--单表的增删改查/GET和POST/request相关知识点回顾
- 一次操作系统报错OutOfMemory Error的处理记录
- java UDP传输
- slot的使用方法
- 【t066】致命的珠宝
- react + webpack 多页面搭建