题解：AT_joi2019ho_e 珍しい都市 (Unique Cities)
lucky_baizq
·
·
题解
F.P6118 [JOI 2019 Final] 独特的城市 / Unique Cities - 洛谷
题意：一棵树，每个点有颜色，对于每个点为根，你需要知道其最长链上该深度的点唯一的点的颜色种类数。
题解：结论，每个点为根的最长链一定是以该树的直径两端点其一为端点的链，否则直径长度会变大。
细节：
1. 父节点入栈。
2. 将栈中节点到这个点深度 $\leq$ 这个点的次长链深度的弹出
3. 遍历最长链儿子。
4. 将栈中节点到这个点距离 $\leq$ 这个点向下最长链的弹出。
5. 计算这个点答案：桶里面的元素个数。
6. 处理其他儿子。
7. 回溯，如果该点有父亲，将父节点弹出。
说明，每次 dfs 到一个点是就是考虑以这个点为根，所以上述操作就好理解了。
Code：他明白 他明白 我给不起~！
```
#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;
}
```