Link
Question
给出一个根为 \(1\) 的树，需要将树分成几个块每个块，一个块中的节点需要满足以下条件中的一个：
-
对于所有的 \(u,v \in S,\ u \neq v\) ，满足 \(u \in subtree(v)\) 或 \(v \in subtree(u)\)
-
对于所有的 \(u,v \in S,\ u \neq v\) ，满足 \(u \not\in subtree(v)\) 且 \(v \not\in subtree(u)\)
求把树分成的最小块数
Solve
先翻译题目，第一个条件是一条链上的点满足，第二个条件是不同子树上的点满足
只考虑第一种情况，贪心的去想，如果选了 \(x\) ，那么再选一个 \(x\) 的子节点并不会增加块数，那么就尽可能多得去选择，也就是取 \(x\) 往下长的链，那么块数就是长链剖分后的链数
只考虑第二种情况，如果给定一颗树，那么最少的块数就是数最深的节点的深度
因为假设选了 \(x\) ，那么 \(x\) 的祖先节点就不能和 \(x\) 在一个块里面，所以假设 \(x\) 的深度为 \(dep[x]\) 则，这条链就需要开 \(dep[x]\) 个块，每个块一个节点，对于不同链的节点，把深度相同的放在一个块里面，所以块数就是最深的那个点的深度
对于一颗树，我们从根节点找最长的链，我们发现，最长链的长度就是 \(Max(dep[x])\) ,但由于不知道到底要取多少条链，就枚举链的条数。贪心的想，我们肯定先取长的链，就先预处理出每条链的长度，设为 \(Len_i\) ，假设取了 \(i\) 条链，剩下的节点需要分的块数就是 \(Len_{i+1}\) 所以，总的块数就是 \(i+Len_{i+1}\)，求一个最小值就是答案
Code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ret=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
const int maxn=1e6+5;
vector<int> dep;
vector<vector<int> > E;
vector<int> son;
vector<int> p;
void dfs1(int x){
for(auto u: E[x]){
dfs1(u);
if(son[x]==0||dep[u]>dep[son[x]]) son[x]=u;
}
dep[x]=dep[son[x]]+1;
}
void dfs2(int x,int now_l){
if(!son[x]) p.push_back(now_l);
else {
dfs2(son[x],now_l+1);
for(auto u:E[x]) {
if(u!=son[x])
dfs2(u,1);
}
}
}
inline void solve(){
int N=read();
p.clear();
dep.assign(N+1,0);
son.assign(N+1,0);
E.resize(N+1);
for(auto& x:E){
x.clear();
}
for(int i=2;i<=N;i++){
int fa=read();
E[fa].push_back(i);
}
dfs1(1);
dfs2(1,1);
sort(p.begin(),p.end(),greater<int>());
int num=p.size(),ans=num;
for(int i=0;i<num-1;i++){
int now_ans=i+p[i+1]+1;
ans=min(now_ans,ans);
}
cout<<ans<<endl;
return ;
}
int main(){
freopen("L.in","r",stdin);
int T=read();
while(T--) solve();
}