当前位置:网站首页>HYSBZ 2243 染色 (树链拆分)
HYSBZ 2243 染色 (树链拆分)
2022-07-05 21:39:00 【全栈程序员站长】
大家好,又见面了,我是全栈君
做题情绪:这题思路好想。调试代码调试了好久。第一次写线段树区间合并。
解题思路:
树链剖分 + 线段树区间合并
线段树的端点记录左右区间的颜色。颜色数目。合并的时候就用区间合并的思想。
还要注意一点。在由一条链转到还有一条链的时候要推断当前节点是否与父亲节点是否同一种颜色。
代码:
#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)
{
// 左
T[L(x)].lc = T[L(x)].rc = T[L(x)].add = T[x].add ; T[L(x)].num = 1 ;
// 右
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) // 更新某个区间
{
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 ;
}
版权声明:本文博客原创文章,博客,未经同意,不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/117566.html原文链接:https://javaforall.cn
边栏推荐
- ESP32
- Zhang Lijun: penetrating uncertainty depends on four "invariants"
- Defect detection - Halcon surface scratch detection
- What should I do to prepare for the interview algorithm position during school recruitment?
- Cross end solution to improve development efficiency rapidly
- SQL common syntax records
- Aitm2-0002 12s or 60s vertical combustion test
- Clion configures Visual Studio (MSVC) and JOM multi-core compilation
- Simple interest mode - lazy type
- Learning notes of statistical learning methods -- Chapter 1 Introduction to statistical learning methods
猜你喜欢
校招期间 准备面试算法岗位 该怎么做?
Why can't Chinese software companies produce products? Abandon the Internet after 00; Open source high-performance API gateway component of station B | weekly email exclusive to VIP members of Menon w
Wood board ISO 5660-1 heat release rate mapping test
MySQL InnoDB Architecture Principle
使用Aspect制作全局异常处理类
Access Zadig self-test environment outside the cluster based on ingress controller (best practice)
PIP install beatifulsoup4 installation failed
Deployment of Jenkins under win7
SQL knowledge leak detection
Teach yourself to train pytorch model to Caffe (2)
随机推荐
Modifiers of attributes of TS public, private, protect
[daily training -- Tencent select 50] 89 Gray code (only after seeing the solution of the problem)
Establishment of terminal security capability verification environment and penetration test records
postgres 建立连接并删除记录
Longest swing sequence [greedy practice]
事项研发工作流全面优化|Erda 2.2 版本如“七”而至
Alibaba cloud award winning experience: build a highly available system with polardb-x
Simple interest mode - lazy type
R语言【数据管理】
int GetMonth( ) const throw( );后面的throw( )什么意思?
Haas506 2.0 development tutorial - Alibaba cloud OTA - PAC firmware upgrade (only supports versions above 2.2)
Making global exception handling classes with aspect
第05章_存储引擎
Robot framework setting variables
Simple interest mode - evil Chinese style
Chapter 05_ Storage engine
Four components of logger
postgis 安装地理信息扩展
【日常训练】729. 我的日程安排表 I
Five layer network protocol