当前位置:网站首页>Ybtoj coloring plan [tree chain dissection, segment tree, tarjan]
Ybtoj coloring plan [tree chain dissection, segment tree, tarjan]
2022-07-06 03:44:00 【QuantAsk】
On the subject
The main idea of the topic
give n n n A tree at a point , Each dot has a color a i a_i ai, You can choose one color at a time and turn it all into another .
Find at least how many operations can turn a color into a complete connected block .
1 ≤ k ≤ n ≤ 2 × 1 0 5 1\leq k\leq n\leq 2\times 10^5 1≤k≤n≤2×105
Their thinking
Consider if we want to turn a color into a connecting block , First of all, we have to assimilate all the smallest connected subgraphs that currently contain its color dots , And after assimilating these colors, you may need to assimilate more colors .
This is a process similar to running chart , We can consider building an edge , If the color A A A Need color B B B that A → B A\rightarrow B A→B, Finally, we can find a point to get the least number of points .
As for how to optimize the mapping process , Let's split the tree chain + Maintain each node on the segment tree , Then each node is connected to the corresponding color .
Then for a color, we follow the dot d f s dfs dfs Sequence , Then, the path between the adjacent points of the ending connection is exactly twice the generated subgraph of its color , It's good to use tree chain to divide and connect the edges .
As for running after building the map tarjan You can find the answer
Time complexity : O ( n log 2 n ) O(n\log^2 n) O(nlog2n)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
using namespace std;
const int N=2e5+10,M=N*5;
struct node{
int to,next;
}a[N<<1];
int n,k,cnt,tot,c[N],ls[N],fa[N],siz[N];
int seg[N],id[N],top[N],son[N],dep[N];
int num,dfc,p[M],dfn[M],low[M],col[M],f[M],in[M];
bool ins[N];stack<int> s;vector<int> v[N],G[M];
void addl(int x,int y){
a[++tot].to=y;
a[tot].next=ls[x];
ls[x]=tot;return;
}
void dfs1(int x){
dep[x]=dep[fa[x]]+1;siz[x]=1;
for(int i=ls[x];i;i=a[i].next){
int y=a[i].to;
if(y==fa[x])continue;
fa[y]=x;dfs1(y);siz[x]+=siz[y];
if(siz[y]>siz[son[x]])son[x]=y;
}
return;
}
void dfs2(int x){
seg[++cnt]=x;id[x]=cnt;
if(son[x]){
top[son[x]]=top[x];
dfs2(son[x]);
}
for(int i=ls[x];i;i=a[i].next){
int y=a[i].to;
if(y==fa[x]||y==son[x])continue;
top[y]=y;dfs2(y);
}
return;
}
void Build(int x,int L,int R){
p[x]=++cnt;
if(L==R){
G[p[x]].push_back(c[seg[L]]);return;}
int mid=(L+R)>>1;
Build(x*2,L,mid);Build(x*2+1,mid+1,R);
G[p[x]].push_back(p[x*2]);
G[p[x]].push_back(p[x*2+1]);
return;
}
void Change(int x,int L,int R,int l,int r,int vp){
if(L==l&&R==r){
G[vp].push_back(p[x]);return;}
int mid=(L+R)>>1;
if(r<=mid)Change(x*2,L,mid,l,r,vp);
else if(l>mid)Change(x*2+1,mid+1,R,l,r,vp);
else Change(x*2,L,mid,l,mid,vp),Change(x*2+1,mid+1,R,mid+1,r,vp);
return;
}
void Recovery(int x,int y,int s){
// printf("%d %d %d\n",x,y,s);
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
Change(1,1,n,id[top[x]],id[x],s);x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
Change(1,1,n,id[x],id[y],s);
return;
}
void tarjan(int x){
dfn[x]=low[x]=++dfc;
ins[x]=1;s.push(x);
for(int i=0;i<G[x].size();i++){
int y=G[x][i];
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(ins[y])
low[x]=min(low[x],dfn[y]);
}
if(low[x]==dfn[x]){
int y;++num;
do{
y=s.top();s.pop();ins[y]=0;
f[num]+=(y<=k);col[y]=num;
}while(y!=x);
}
return;
}
bool cmp(int x,int y)
{
return id[x]<id[y];}
int main()
{
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=1;i<n;i++){
int x,y;
scanf("%d%d",&x,&y);
addl(x,y);addl(y,x);
}
for(int i=1;i<=n;i++)
scanf("%d",&c[i]),v[c[i]].push_back(i);
dfs1(1);top[1]=1;dfs2(1);
cnt=k;Build(1,1,n);
for(int i=1;i<=k;i++){
if(v[i].size()<2)continue;
sort(v[i].begin(),v[i].end(),cmp);
for(int j=1;j<v[i].size();j++)
Recovery(v[i][j-1],v[i][j],i);
}
for(int i=1;i<=cnt;i++)
if(!dfn[i])tarjan(i);
for(int x=1;x<=cnt;x++){
for(int i=0;i<G[x].size();i++){
int y=G[x][i];
if(col[x]==col[y])continue;
in[col[x]]++;
}
}
int ans=k;
for(int i=1;i<=k;i++)
if(!in[col[i]])ans=min(ans,f[col[i]]);
printf("%d\n",ans-1);
return 0;
}
边栏推荐
- MADDPG的pythorch实现——(1)OpenAI MADDPG环境配置
- BUAA计算器(表达式计算-表达式树实现)
- Indicator system of KQI and KPI
- mysql关于自增长增长问题
- Cross origin cross domain request
- Schnuka: 3D vision detection application industry machine vision 3D detection
- 施努卡:什么是视觉定位系统 视觉系统如何定位
- Brush questions in summer -day3
- Pytorch基础——(2)张量(tensor)的数学运算
- 潘多拉 IOT 开发板学习(HAL 库)—— 实验9 PWM输出实验(学习笔记)
猜你喜欢
KS003基于JSP和Servlet实现的商城系统
1、工程新建
【SLAM】lidar-camera外参标定(港大MarsLab)无需二维码标定板
Canvas cut blocks game code
SAP ALV单元格级别设置颜色
Alibaba testers use UI automated testing to achieve element positioning
SWC introduction
施努卡:3d视觉检测应用行业 机器视觉3d检测
Image super-resolution using deep convolutional networks(SRCNN)解读与实现
Princeton University, Peking University & UIUC | offline reinforcement learning with realizability and single strategy concentration
随机推荐
记录一下逆向任务管理器的过程
RT-Thread--Lwip之FTP(2)
Blue Bridge Cup - day of week
C#(三十一)之自定义事件
3.2 detailed explanation of rtthread serial port device (V2)
JS音乐在线播放插件vsPlayAudio.js
自动化测试怎么规范部署?
Ethernet port &arm & MOS &push-pull open drain &up and down &high and low sides &time domain and frequency domain Fourier
BUAA calculator (expression calculation - expression tree implementation)
【SLAM】lidar-camera外参标定(港大MarsLab)无需二维码标定板
2.1 rtthread pin device details
2.2 STM32 GPIO操作
Take you to wechat applet development in 3 minutes
Record the process of reverse task manager
教你用Pytorch搭建一个自己的简单的BP神经网络( 以iris数据集为例 )
施努卡:3d视觉检测应用行业 机器视觉3d检测
简易博客系统
js凡客banner轮播图js特效
Quick sort function in C language -- qsort
After five years of testing in byte, I was ruthlessly dismissed in July, hoping to wake up my brother who was paddling