【长链剖分】icpc 2022西安 L

阳光穿透心脏的1/2处 2024-03-22 23:32 78阅读 0赞

[Problem - L - Codeforces][]

题意：

![1223aff54a5d44cebad6e12b5daf02c7.png][]

思路：

![0d1c924b4a5b4f849ad067aa955dfea2.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    
    vector<int> G[mxn],lp;
    
    int N,Fa;
    int son[mxn],len[mxn];
    
    void dfs1(int u,int fa){
    	for(auto v:G[u]){
    		if(v==fa) continue;
    		dfs1(v,u);
    		if(len[v]>len[son[u]]) son[u]=v;
    	}
    	len[u]=len[son[u]]+1;
    }
    void dfs2(int u,int dep,int fa){
    	if(!son[u]){
    		lp.push_back(dep);
    	}else{
    		dfs2(son[u],dep+1,u);
    		for(auto v:G[u]){
    			if(v==fa) continue;
    			if(v!=son[u]){
    				dfs2(v,1,u);
    			}
    		}
    	}
    }
    void solve(){
    	cin>>N;
    	lp.clear();
    	for(int i=1;i<=N;i++){
    		G[i].clear();
    		len[i]=0;
    		son[i]=0;
    	}
    	for(int i=2;i<=N;i++){
    		cin>>Fa;
    		G[Fa].push_back(i);
    		G[i].push_back(Fa);
    	}
    	dfs1(1,0);
    	dfs2(1,1,0);
    	sort(lp.begin(),lp.end(),greater<int>());
    	int ans=lp.size();
    	for(int i=0;i<lp.size();i++){
    		ans=min(ans,lp[i]+i);
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - L - Codeforces]: https://codeforces.com/gym/104077/problem/L
[1223aff54a5d44cebad6e12b5daf02c7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/700b2fbd44064f22a7844b564ca36b45.png
[0d1c924b4a5b4f849ad067aa955dfea2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/977b86a677a945639e3e6cd88520f9cf.png

发表评论取消回复

表情：

评论列表（有 0 条评论，78人围观）

还没有评论，来说两句吧...

相关阅读

相关【长链剖分】icpc 2022西安 L

[Problem - L - Codeforces][] 题意： ![1223aff54a5d44cebad6e12b5daf02c7.png][] 思路： ![0d1

阳光穿透心脏的1/2处/ 2024年03月22日 23:32/ 0 赞/ 79 阅读

相关长链剖分洛谷dominant indices

题意翻译给出一棵有根树，对于每个节点x，定义一个无穷序列d，其中d(x,i)表示以x为根节点的子树中到x的距离恰好为i的点的个数，i=0~无穷，现在对每个点x，希望求出

悠悠/ 2023年06月03日 05:52/ 0 赞/ 18 阅读

相关啊哈树链剖分——重链剖分（之后学完splay就搞虚实链剖分）

阿巴阿巴阿巴。。。。后续会加splay+虚实链剖分学习博客：[https://blog.csdn.net/qq\_43326267/article/details/8979

蔚落/ 2022年11月28日 10:36/ 0 赞/ 155 阅读

相关树链剖分入门讲解

“在一棵树上进行路径的修改、求极值、求和”乍一看只要线段树就能轻松解决，实际上，仅凭线段树是不能搞定它的。我们需要用到一种貌似高级的复杂算法——树链剖分。树链，就是树上的路

拼搏现实的明天。/ 2022年07月17日 02:18/ 0 赞/ 191 阅读

相关 PowerOJ1179-树链剖分

题目链接： [PowerOj1179][] 1179: 我要10个G Time Limit: 8500 MS Memory Limit: 209715

傷城~/ 2022年06月17日 12:20/ 0 赞/ 229 阅读

相关树链剖分详解

转载请注明出处，部分内容引自banananana大神的博客 -------------------- 树链剖分就是将树分割成多条链，然后利用数据结构（线段树、树状数组等）来

谁践踏了优雅/ 2022年05月09日 05:58/ 0 赞/ 216 阅读

相关 [模板] 长链剖分

长链剖分 [长链剖分学习总结 | Bill Yang's Blog][_ Bill Yang_s Blog] 简介对每个节点 \\(p\\), 定义 \\

刺骨的言语ヽ痛彻心扉/ 2022年01月08日 00:41/ 0 赞/ 229 阅读

相关树链剖分

[咕咕咕][Link 1] 一、功能将树从x到y结点最短路径上所有节点的值都加上z 求树从x到y结点最短路径上所有节点的值之和将以x为根节点的子

柔情只为你懂/ 2021年10月24日 02:44/ 0 赞/ 359 阅读

相关树链剖分

自己码力好弱，，洛谷：树链剖分模板 include<bits/stdc++.h> using namespace std; const int M

刺骨的言语ヽ痛彻心扉/ 2021年10月23日 06:49/ 0 赞/ 370 阅读

相关 8.4 树链剖分

详解：https://www.cnblogs.com/ivanovcraft/p/9019090.html 树链剖分的本质是序以尽量走重链为序，使一棵树的结点尽量集

柔情只为你懂/ 2021年10月18日 08:52/ 0 赞/ 356 阅读