Ybtoj coloring plan [tree chain dissection, segment tree, tarjan]

On the subject

---

The main idea of the topic

give $n$ A tree at a point , Each dot has a color $a_i$, 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\le k\le n\le 2\times 10^5$

---

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$ Need color $B$ that $A\to 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 $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)$

---

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;
}