题解：AT_joi2019ho_e 珍しい都市 (Unique Cities)

F.P6118 [JOI 2019 Final] 独特的城市 / Unique Cities - 洛谷

题意：一棵树，每个点有颜色，对于每个点为根，你需要知道其最长链上该深度的点唯一的点的颜色种类数。

题解：结论，每个点为根的最长链一定是以该树的直径两端点其一为端点的链，否则直径长度会变大。

2

种情况分讨一下，取最大值就做完了。

细节：

父节点入栈。
将栈中节点到这个点深度 $\leq$ 这个点的次长链深度的弹出
遍历最长链儿子。
将栈中节点到这个点距离 $\leq$ 这个点向下最长链的弹出。
计算这个点答案：桶里面的元素个数。
处理其他儿子。
回溯，如果该点有父亲，将父节点弹出。

说明，每次 dfs 到一个点是就是考虑以这个点为根，所以上述操作就好理解了。

Code：他明白他明白我给不起~！

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second

const int N=500010;

vector<int> f[N];

int dis[N],far,s,t1,mx[N],siz,shu[N],m[N],col[N],_,ans[N],g[N],n,x,y;

void get(int u,int f1){
	for(int v:f[u]){
		if(v==f1)continue;
		dis[v]=dis[u]+1;
		get(v,u);
	}
	mx[u]=max(mx[u],dis[u]);
	if(dis[far]<dis[u])far=u;
}

int dep[N],son[N][2],id,t[N];

void dfs(int u,int f1){
	dep[u]=dep[f1]+1;
	son[u][0]=son[u][1]=0;
	for(int v:f[u]){
		if(v==f1)continue;
		dfs(v,u);
		if(g[v]>g[son[u][0]]){
			son[u][1]=son[u][0];
			son[u][0]=v;
		}else if(g[v]>g[son[u][1]]){
			son[u][1]=v;
		}
	}
	g[u]=g[son[u][0]]+1;
}

stack<int> st;

void dfs1(int u,int f1){
	if(f1){
		st.push(f1);
		t[col[f1]]++;
		if(t[col[f1]]==1)id++;
	}
	if(son[u][0]){
		while(!st.empty()&&dep[st.top()]>=dep[u]-g[son[u][1]]){
			t[col[st.top()]]--;if(t[col[st.top()]]==0)id--;st.pop();
		}
		dfs1(son[u][0],u);
	}
	while(!st.empty()&&dep[st.top()]>=dep[u]-g[son[u][0]]){
		t[col[st.top()]]--;if(t[col[st.top()]]==0)id--;st.pop();
	}
	for(int v:f[u]){
		if(v==f1||v==son[u][0])continue;
		dfs1(v,u);
	}
	ans[u]=max(ans[u],id);
	if(!st.empty()&&st.top()==f1){
		t[col[st.top()]]--;if(t[col[st.top()]]==0)id--;st.pop();
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    cin>>n>>_;
	for(int i=1;i<n;i++){
		cin>>x>>y;
		f[x].push_back(y);
		f[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		cin>>col[i];
	}
    s=1;get(s,0);s=far;memset(dis,0,sizeof dis);far=0;get(s,0);t1=far;
//	siz=dis[t];
//    memset(mx,0,sizeof mx);get(s,0);memset(dis,0,sizeof dis);get(t,0);
//    for(int i=1;i<=n;i++){
//    	if(dis[i]==mx[i])shu[i]=t,m[i]=mx[i]-(siz-mx[i]);
//    	else shu[i]=s,m[i]=mx[i]-(siz-mx[i]);
//	}
	dfs(s,0);dfs1(s,0);memset(son,0,sizeof son);
	dfs(t1,0);dfs1(t1,0);
	for(int i=1;i<=n;i++)
	cout<<ans[i]<<"\n";
    return 0;
}

题解：AT_joi2019ho_e 珍しい都市 (Unique Cities)

文章操作

相关推荐

评论

题解：AT_joi2019ho_e 珍しい都市 (Unique Cities)