AC日记——#2054. 「TJOI / HEOI2016」树
2024-09-13 00:45:10
思路:
线段树;
代码:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 100005
#define maxm maxn<<1
#define maxtree maxn<<2
int n,head[maxn],E[maxm],V[maxm],cnt,m,deep[maxn],li[maxn],ri[maxn];
int val[maxtree],L[maxtree],R[maxtree],mid[maxtree],key[maxtree],tmp1,tmp2;
bool if_[maxtree];
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)
{
deep[now]=deep[fa]+,li[now]=++cnt;
for(int i=head[now];i;i=E[i])
{
if(V[i]==fa) continue;
dfs(V[i],now);
}
ri[now]=cnt;
}
void build(int now,int l,int r)
{
L[now]=l,R[now]=r;
if(l==r)
{
if_[now]=true,val[now]=,key[now]=;
return;
}
mid[now]=l+r>>;
build(now<<,l,mid[now]);
build(now<<|,mid[now]+,r);
}
void change(int now,int l,int r,int va,int ke)
{
if(L[now]>=l&&R[now]<=r)
{
if(if_[now])
{
if(ke>key[now])key[now]=ke,val[now]=va;
}
else if_[now]=true,key[now]=ke,val[now]=va;
return;
}
if(l<=mid[now]) change(now<<,l,r,va,ke);
if(r>mid[now]) change(now<<|,l,r,va,ke);
}
void query(int now,int to)
{
if(if_[now]&&key[now]>tmp2) tmp1=val[now],tmp2=key[now];
if(L[now]==R[now]) return;
if(to<=mid[now]) query(now<<,to);
else query(now<<|,to);
}
int main()
{
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;
}
cnt=,dfs(,),build(,,n);
char op[];
for(int i=;i<=m;i++)
{
scanf("%s",op),in(u);
if(op[]=='C') change(,li[u],ri[u],u,deep[u]);
else tmp1=,tmp2=,query(,li[u]),printf("%d\n",tmp1);
}
return ;
}
最新文章
- 20145227&;20145201 《信息安全系统设计基础》实验三
- Error retrieving parent for item: No resource found that matches the given name &#39;android:TextAppearance.Material.Widget.Button.Inverse&#39;.
- 安装依赖包时--save-dev以及-save的区别及意义
- Xcode全局断点
- DHCP服务自动分配IP地址原理
- core文件找不到了
- oracle监控脚本【转】
- Oracle-表被锁住
- 网站集群架构(LVS负载均衡、Nginx代理缓存、Nginx动静分离、Rsync+Inotify全网备份、Zabbix自动注册全网监控)--技术流ken
- 基于vue-cli,sass,vant的移动端项目
- surfer画世界频率分布图(等高线、地点标注)
- .net 连接 Oracle 可能需要配置
- jmeter解决登录token获取
- Sencha Touch 实战开发培训 视频教程 第二期 第三节
- SQL Fundamentals: 分组统计查询(FROM-WHERE-GROUPBY-HAVING-SELECT-ORDER BY)
- joinablequeue模块 生产者消费者模型 Manager模块 进程池 管道
- 怎样让你的APK跑在 com.android.phone 进程
- 洛谷 P4211 [LNOI2014]LCA (树链剖分+离线)
- MySql Replication基本原理
- 利用Django中间件middleware解决用户未登录问题(转)
热门文章
- Python3 字典 get() 方法
- Python高级语法总结
- UESTC--1300
- laravel 5.5 在构造函数使用Session
- CollectionUtils.isEqualCollection的用法
- JS获取URL中参数值(QueryString)的4种方法分享
- 从零搭建SSM框架(五)Maven实现Tomcat热部署
- hihocoder1415 后缀数组三&#183;重复旋律3
- Spring Boot工程结构推荐
- 【洛谷 P4219】 [BJOI2014]大融合(LCT)