当前位置:网站首页>Hysbz 2243 staining (tree chain splitting)
Hysbz 2243 staining (tree chain splitting)
2022-07-05 21:44:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack
The mood of doing the topic : This question is very thoughtful . Debugging code debugging for a long time . Write segment tree interval merging for the first time .
Their thinking :
The tree chain splits + Segment tree interval merging
The endpoint of the line segment tree records the color of the left and right intervals . Number of colors . When merging, use the idea of interval merging .
One more thing to note . When changing from one chain to another, it is necessary to infer whether the current node is the same color as the parent node .
Code :
#include<iostream>
#include<sstream>
#include<map>
#include<cmath>
#include<fstream>
#include<queue>
#include<vector>
#include<sstream>
#include<cstring>
#include<cstdio>
#include<stack>
#include<bitset>
#include<ctime>
#include<string>
#include<cctype>
#include<iomanip>
#include<algorithm>
using namespace std ;
#define INT __int64
#define L(x) (x * 2)
#define R(x) (x * 2 + 1)
const int INF = 0x3f3f3f3f ;
const double esp = 0.0000000001 ;
const double PI = acos(-1.0) ;
const int mod = 1e9 + 7 ;
const int MY = 1400 + 5 ;
const int MX = 100000 + 5 ;
int n ,m ,idx ,num ;
int head[MX] ,ti[MX] ,top[MX] ,dep[MX] ,siz[MX] ,son[MX] ,father[MX] ,g[MX] ;
struct Edge
{
int v ,next ;
}E[MX*2] ;
void addedge(int u ,int v)
{
E[num].v = v ; E[num].next = head[u] ; head[u] = num++ ;
E[num].v = u ; E[num].next = head[v] ; head[v] = num++ ;
}
void dfs_find(int u ,int fa)
{
dep[u] = dep[fa] + 1 ;
siz[u] = 1 ;
son[u] = 0 ;
father[u] = fa ;
for(int i = head[u] ;i != -1 ;i = E[i].next)
{
int v = E[i].v ;
if(v == fa) continue ;
dfs_find(v ,u) ;
siz[u] += siz[v] ;
if(siz[son[u]] < siz[v]) son[u] = v ;
}
}
void dfs_time(int u ,int fa)
{
ti[u] = idx++ ;
top[u] = fa ;
if(son[u]) dfs_time(son[u] ,top[u]) ;
for(int i = head[u] ;i != -1 ;i = E[i].next)
{
int v = E[i].v ;
if(v == father[u] || v == son[u]) continue ;
dfs_time(v ,v) ;
}
}
struct node
{
int le ,rt ,lc ,rc ,num ,add ;
}T[MX*4] ;
void build(int x ,int le ,int rt)
{
T[x].le = le ; T[x].rt = rt ;
T[x].lc = T[x].rc = T[x].add = -1 ;
T[x].num = 0 ;
if(le == rt) return ;
int Mid = (le + rt)>>1 ;
build(L(x) ,le ,Mid) ;
build(R(x) ,Mid + 1 ,rt) ;
}
void push_down(int x)
{
if(T[x].add != -1)
{
// Left
T[L(x)].lc = T[L(x)].rc = T[L(x)].add = T[x].add ; T[L(x)].num = 1 ;
// Right
T[R(x)].lc = T[R(x)].rc = T[R(x)].add = T[x].add ; T[R(x)].num = 1 ;
T[x].add = -1 ;
}
}
void push_up(int x)
{
T[x].num = T[L(x)].num + T[R(x)].num ;
if(T[L(x)].rc == T[R(x)].lc)
T[x].num -- ;
T[x].lc = T[L(x)].lc ; T[x].rc = T[R(x)].rc ;
}
void update(int x ,int le ,int rt ,int w) // Update an interval
{
if(T[x].le == le && T[x].rt == rt)
{
T[x].add = w ;
T[x].lc = w ; T[x].rc = w ; T[x].num = 1 ;
return ;
}
push_down(x) ;
int Mid = (T[x].le + T[x].rt)>>1 ;
if(le > Mid) update(R(x) ,le ,rt ,w) ;
else if(rt <= Mid) update(L(x) ,le ,rt ,w) ;
else
{
update(L(x) ,le ,Mid ,w) ;
update(R(x) ,Mid+1 ,rt ,w) ;
}
push_up(x) ;
}
int Query(int x ,int le ,int rt)
{
if(T[x].le == le && T[x].rt == rt)
return T[x].num ;
int Mid = (T[x].le + T[x].rt)>>1 ;
push_down(x) ;
if(le > Mid) return Query(R(x) ,le ,rt) ;
else if(rt <= Mid) return Query(L(x) ,le ,rt) ;
else
{
int mx = 0 ;
if(T[L(x)].rc == T[R(x)].lc)
mx = -1 ;
return Query(L(x) ,le ,Mid) + Query(R(x) ,Mid+1 ,rt) + mx ;
}
push_up(x) ;
}
int Querynode(int x ,int pos)
{
if(T[x].le == T[x].rt)
return T[x].lc ;
int Mid = (T[x].le + T[x].rt)>>1 ;
push_down(x) ;
if(pos <= Mid)
return Querynode(L(x) ,pos) ;
else return Querynode(R(x) ,pos) ;
push_up(x) ;
}
void LCAC(int u ,int v ,int w)
{
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]])
swap(u ,v) ;
update(1 ,ti[top[u]] ,ti[u] ,w) ;
u = father[top[u]] ;
}
if(dep[u] > dep[v])
swap(u ,v) ;
update(1 ,ti[u] ,ti[v] ,w) ;
}
int LCAQ(int u ,int v)
{
int ans = 0 ;
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]])
swap(u ,v) ;
ans += Query(1 ,ti[top[u]] ,ti[u]) ;
if(Querynode(1 ,ti[top[u]]) == Querynode(1 ,ti[father[top[u]]]))
ans-- ;
u = father[top[u]] ;
}
if(dep[u] > dep[v])
swap(u ,v) ;
ans += Query(1 ,ti[u] ,ti[v]) ;
return ans ;
}
int main()
{
while(~scanf("%d%d" ,&n ,&m))
{
int u ,v ,w ;
num = 0 ;
memset(head ,-1 ,sizeof(head)) ;
for(int i = 1 ;i <= n ; ++i)
scanf("%d" ,&g[i]) ;
for(int i = 1 ;i < n ; ++i)
{
scanf("%d%d" ,&u ,&v) ;
addedge(u ,v) ;
}
dep[1] = siz[0] = 0 ;
dfs_find(1 ,1) ;
idx = 1 ;
dfs_time(1 ,1) ;
build(1 ,1 ,n) ;
for(int i = 1 ;i <= n ; ++i)
update(1 ,ti[i] ,ti[i] ,g[i]) ;
char s[5] ;
for(int i = 0 ;i < m ; ++i)
{
scanf("%s" ,s) ;
scanf("%d%d" ,&u ,&v) ;
if(s[0] == 'C')
{
scanf("%d" ,&w) ;
LCAC(u ,v ,w) ;
}
else if(s[0] == 'Q')
printf("%d\n" ,LCAQ(u ,v)) ;
}
}
return 0 ;
}
Copyright notice : This article is an original blog article , Blog , Without consent , Shall not be reproduced .
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/117566.html Link to the original text :https://javaforall.cn
边栏推荐
- Teach yourself to train pytorch model to Caffe (III)
- Kingbasees v8r3 data security case - audit record clearing case
- sql常用语法记录
- 华为云ModelArts文本分类–外卖评论
- Kingbasees v8r3 cluster maintenance case -- online addition of standby database management node
- SQL common syntax records
- xlrd常见操作
- 854. 相似度为 K 的字符串 BFS
- 冯唐“春风十里不如你”数字藏品,7月8日登录希壤!
- Scenario interview: ten questions and ten answers about distributed locks
猜你喜欢
Feng Tang's "spring breeze is not as good as you" digital collection, logged into xirang on July 8!
DBeaver同时执行多条insert into报错处理
MySQL InnoDB Architecture Principle
总结出现2xx、3xx、4xx、5xx状态码的原因
Clickhouse copy paste multi line SQL statement error
MMAP learning
MATLAB | App Designer·我用MATLAB制作了一款LATEX公式实时编辑器
华为联机对战如何提升玩家匹配成功几率
Interviewer: will concurrent programming practice meet? (detailed explanation of thread control operation)
Realize the function of verifying whether the user has completed login when browsing the page
随机推荐
R language [data management]
crm创建基于fetch自己的自定义报告
Implementing Lmax disruptor queue from scratch (IV) principle analysis of multithreaded producer multiproducersequencer
Some common processing problems of structural equation model Amos software
Four components of logger
深信服X计划-网络协议基础 DNS
Experienced inductance manufacturers tell you what makes the inductance noisy. Inductance noise is a common inductance fault. If the used inductance makes noise, you don't have to worry. You just need
POJ 3237 tree (tree chain splitting)
Simple interest mode - lazy type
datagrid直接编辑保存“设计缺陷”
2022-07-03-CKA-粉丝反馈最新情况
Alibaba cloud award winning experience: build a highly available system with polardb-x
Feng Tang's "spring breeze is not as good as you" digital collection, logged into xirang on July 8!
@Validated basic parameter verification, grouping parameter verification and nested parameter verification
Simple interest mode - evil Chinese style
Yolov5 training custom data set (pycharm ultra detailed version)
递归查询多级菜单数据
int GetMonth( ) const throw( );后面的throw( )什么意思?
Xlrd common operations
How can Huawei online match improve the success rate of player matching