題目

https://gmoj.net/senior/#main/show/6807

題解

轉化題意，可以發現，這道題就是選擇一個根，使得它的某個子樹內包含所有顏色，求滿足條件的子樹的最大深度，

比賽時我的思路是刪掉以某個兒子為根的子樹（或以當前點為根的子樹外的部分），結果發現這樣子處理不了刪掉以孫子為根的子樹的情況，最終掛在這道題上了，

其實應該考慮另外的處理方式：刪掉某棵子樹或刪掉某棵子樹外的全部點，這里的刪掉指的是不選擇這些點，若答案不等于1，根就在這些點中，

分別考慮這兩種情況：

1. 當我刪掉一個子樹時，說明這個子樹外包含所有的顏色，但是這個條件比較難判斷，于是考慮這個子樹不能被刪去時滿足什么條件，顯然是這個子樹外缺少某種顏色，即這種顏色全都在這個子樹內，對于每一種顏色，把它們的lca求出來，lca到根的路徑上的點就是不能刪掉子樹的點，用倍增lca O ( n log ? 2 n ) O(n\log_2n) O(nlog2?n)地處理即可（但是這樣子常數巨大，優化后面會講）；
2. 當我刪掉一個子樹外的所有點時，說明這個子樹內包含所有點，發現樹上處理起來很麻煩（可以線段樹合并，但是空間和時間都可能爆掉），就把它轉化到序列上（按dfn序排序），雙指標 O ( n ) O(n) O(n)地掃描一下就行了（當然你喜歡的話也可以用主席樹，但是可能會炸空間），

理論上這樣打就能過了，但是我常數太大TLE了……

發現跑得最慢的部分是求一堆點的lca那里，要不開#pragma GCC optimize("O3")過這題勢必要優化這個部分，

這里有一個定理： ? d f n a ≤ d f n b ≤ d f n c , 都 有 l c a ( a , c ) = l c a ( a , b , c ) \forall dfn_a\le dfn_b\le dfn_c,都有 lca(a,c)=lca(a,b,c) ?dfna?≤dfnb?≤dfnc?,都有lca(a,c)=lca(a,b,c)，
證明的話就是 l c a ( a , c ) lca(a,c) lca(a,c)的子樹中必定包含了dfn在 [ a , c ] [a,c] [a,c]中所有點，因此必定也是b的祖先，

有了這個定理就可以將這個部分優化到 O ( m log ? 2 n ) O(m\log_2n) O(mlog2?n)了，足以通過這道題，如果常數太大還是過不了，可以用tarjan lca，

CODE

倍增lca版本，常數稍大：

#include<cstdio>
using namespace std;
#define M 2000005
#define N 1000005
#define C 100005
struct array{int fir[C],nex[N];}a;bool cover[N];
int fir[N],to[M],nex[M],col[N],las[C],b[C],right[N];
int f[N][20],g[N][2],son[N],h[N],dep[N],dfn[N],id[N],siz[N],cnt,s,m;
inline char gc()
{
	static char buf[100005],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100005,stdin),l==r)?EOF:*l++;
}
inline void read(int &x)
{
	char ch;while(ch=gc(),ch<'0'||ch>'9');x=ch-48;
	while(ch=gc(),ch>='0'&&ch<='9') x=x*10+ch-48;
}
inline void inc(int x,int y)
{
	to[++s]=y,nex[s]=fir[x],fir[x]=s;
	to[++s]=x,nex[s]=fir[y],fir[y]=s;
}
inline void swap(int &x,int &y){int z=x;x=y,y=z;}
void dfs(int k)
{
	id[++cnt]=k,dfn[k]=cnt;
	dep[k]=dep[f[k][0]]+1,siz[k]=1;
	for(int i=fir[k];i;i=nex[i]) if(to[i]!=f[k][0])
		f[to[i]][0]=k,dfs(to[i]),siz[k]+=siz[to[i]];
}
inline int mymax(int x,int y){return x>y?x:y;}
inline int getlca(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	for(int i=19;i>=0;--i)
		if(dep[f[u][0]]>=dep[v])
			u=f[u][0];
	if(u==v) return u;
	for(int i=19;i>=0;--i)
		if(f[u][i]^f[v][i])
			u=f[u][i],v=f[v][i];
	return f[u][0];
}
int main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	int n,x,y,l,r,tot=0,ans=0;
	read(n),read(m);
	for(int i=1;i<=n;++i) read(col[i]),a.nex[i]=a.fir[col[i]],a.fir[col[i]]=i;
	for(int i=1;i<n;++i) read(x),read(y),inc(x,y);
	dep[1]=1,dfs(1);
	for(int i=n,tmp,k;i>1;--i)
	{
		tmp=g[id[i]][0]+1,k=f[id[i]][0];
		if(tmp>g[k][0]) g[k][1]=g[k][0],g[k][0]=tmp,son[k]=id[i];
		else if(tmp>g[k][1]) g[k][1]=tmp;
	}
	for(int i=2,k,fa;i<=n;++i) k=id[i],fa=f[k][0],h[k]=mymax(h[fa],g[fa][k==son[fa]])+1;
	for(int j=1;j<20;++j)
		for(int i=1;i<=n;++i)
			f[i][j]=f[f[i][j-1]][j-1];
	for(int i=1,max,min;i<=m;++i) if(a.fir[i])
	{
		max=0,min=N;
		for(int j=a.fir[i];j;j=a.nex[j])
		{
			if(dfn[j]>max) max=dfn[j];
			if(dfn[j]<min) min=dfn[j];
		}
		cover[getlca(id[max],id[min])]=1;
	}
	for(int i=n;i>1;--i) cover[f[id[i]][0]]|=cover[id[i]];
	for(int i=1;i<=m;++i) las[i]=n+1;
	for(int i=n;i;--i) right[i]=las[col[id[i]]],las[col[id[i]]]=i;
	for(int i=1;i<=n;++i) if(!cover[id[i]]) ans=mymax(ans,g[id[i]][0]+1);
	b[col[id[1]]]=1,tot=r=1;
	while(r<=n&&tot<m)
	{
		if(!b[col[id[++r]]]) ++tot;
		++b[col[id[r]]];
	}
	for(l=1;l<=n;++l)
	{
		if(r<=l+siz[id[l]]-1) ans=mymax(ans,h[id[l]]);
		if(!--b[col[id[l]]])
		{
			if(right[l]>n) break;
			for(int i=r+1;i<=right[l];++i) ++b[col[id[i]]];
			r=right[l];
		}
	}
	printf("%d\n",ans+1);
	return 0;
}

tarjan lca版本，代碼稍長：

#include<cstdio>
using namespace std;
#define M 2000005
#define N 1000005
#define C 100005
struct array{int fir[C],nex[N];}a;bool cover[N];
struct query
{
	int fir[N],nex[200005],to[200005],s;
	inline void inc(int x,int y)
	{
		to[++s]=y,nex[s]=fir[x],fir[x]=s;
		to[++s]=x,nex[s]=fir[y],fir[y]=s;
	}
}qry;
int fir[N],to[M],nex[M],col[N],las[C],b[C],right[N];
int f[N],g[N][2],son[N],h[N],dep[N],dfn[N],id[N],siz[N],fa[N],cnt,s,m;
inline char gc()
{
	static char buf[100005],*l=buf,*r=buf;
	return l==r&&(r=(l=buf)+fread(buf,1,100005,stdin),l==r)?EOF:*l++;
}
inline void read(int &x)
{
	char ch;while(ch=gc(),ch<'0'||ch>'9');x=ch-48;
	while(ch=gc(),ch>='0'&&ch<='9') x=x*10+ch-48;
}
inline void inc(int x,int y)
{
	to[++s]=y,nex[s]=fir[x],fir[x]=s;
	to[++s]=x,nex[s]=fir[y],fir[y]=s;
}
inline void swap(int &x,int &y){int z=x;x=y,y=z;}
void dfs(int k)
{
	id[++cnt]=k,dfn[k]=cnt;
	dep[k]=dep[fa[k]]+1,siz[k]=1;
	for(int i=fir[k];i;i=nex[i]) if(to[i]!=fa[k])
		fa[to[i]]=k,dfs(to[i]),siz[k]+=siz[to[i]];
}
inline int mymax(int x,int y){return x>y?x:y;}
int getf(int k){return f[k]==k?k:f[k]=getf(f[k]);}
void getlca(int k)
{
	for(int i=fir[k];i;i=nex[i]) if(to[i]!=fa[k])
		getlca(to[i]),f[to[i]]=k;
	for(int i=qry.fir[k];i;i=qry.nex[i]) if(f[qry.to[i]]!=qry.to[i])
		cover[getf(qry.to[i])]=1;
}
int main()
{
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	int n,x,y,l,r,tot=0,ans=0;
	read(n),read(m);
	for(int i=1;i<=n;++i) read(col[i]),a.nex[i]=a.fir[col[i]],a.fir[col[i]]=i;
	for(int i=1;i<n;++i) read(x),read(y),inc(x,y);
	dep[1]=1,dfs(1);
	for(int i=n,tmp,k;i>1;--i)
	{
		tmp=g[id[i]][0]+1,k=fa[id[i]];
		if(tmp>g[k][0]) g[k][1]=g[k][0],g[k][0]=tmp,son[k]=id[i];
		else if(tmp>g[k][1]) g[k][1]=tmp;
	}
	for(int i=2,k;i<=n;++i) k=id[i],h[k]=mymax(h[fa[k]],g[fa[k]][k==son[fa[k]]])+1;
	for(int i=1,max,min;i<=m;++i) if(a.fir[i])
	{
		max=0,min=N;
		for(int j=a.fir[i];j;j=a.nex[j])
		{
			if(dfn[j]>max) max=dfn[j];
			if(dfn[j]<min) min=dfn[j];
		}
		if(id[max]^id[min]) qry.inc(id[max],id[min]);
		else cover[id[max]]=1;
	}
	for(int i=1;i<=n;++i) f[i]=i;getlca(1);
	for(int i=n;i>1;--i) cover[fa[id[i]]]|=cover[id[i]];
	for(int i=1;i<=m;++i) las[i]=n+1;
	for(int i=n;i;--i) right[i]=las[col[id[i]]],las[col[id[i]]]=i;
	for(int i=1;i<=n;++i) if(!cover[id[i]]) ans=mymax(ans,g[id[i]][0]+1);
	b[col[id[1]]]=1,tot=r=1;
	while(r<=n&&tot<m)
	{
		if(!b[col[id[++r]]]) ++tot;
		++b[col[id[r]]];
	}
	for(l=1;l<=n;++l)
	{
		if(r<=l+siz[id[l]]-1) ans=mymax(ans,h[id[l]]);
		if(!--b[col[id[l]]])
		{
			if(right[l]>n) break;
			for(int i=r+1;i<=right[l];++i) ++b[col[id[i]]];
			r=right[l];
		}
	}
	printf("%d\n",ans+1);
	return 0;
}