专栏文章

题解：P13279 「CZOI-R4」生长的树

XXHZnewlife
P13279题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miowmw8m
此快照首次捕获于
2025/12/03 02:21
3 个月前
此快照最后确认于
2025/12/03 02:21
3 个月前
查看原文
蒟蒻的第一篇题解，求过
推一下自己的专栏
首先，我们可以注意到这道题中节点的编号是没有任何用处的。
由于可以任意填编号，对于符合 T2T_{2} 的点，我们原样填进去，其余节点，我们填大于 nn 的数。
而我们站在完成时的眼光看过去，可以假设我们每次都填了恰好正确的编号。

第一思路

在赛时的紧张环境下，我们很难一下想到正解，于是我们往往可以凭借我们直观感受找到一个第一思路。
样例给了一个很好的示范（记住这句话。
在样例的引导下我们很快就想到了让 T1T_{1} 符合要求的前提必须是——它和 T2T_{2} 一样深，这个条件只能等待时间的流逝。
但一次时间内我们可以操作无数次。所以通过样例，我们可以想到:深度足够之后，再将多余部分全部剪掉。
所以，我们的直观想法就诞生了—— pp 就是深度， qq 就是不满足深度的所有结点的缺失子树个数。

正解

然而——直观思路只能拿到 2020 分。
问题出在哪里呢？
我们不妨考虑一个这样的例子：
如果是刚才的思路，我们一定不假思索地回答：“ 22 33 ”。
但答案却是“ 22 11 ”。
我们的思维被限制在哪里了呢？
“深度足够之后，‘再’将多余部分全部剪掉。”
在此例子中，第一次生长后就可以剪去最右边的的节点了，这样只需要一次操作。
样例真是害人不浅
我们再画几个图就可以直观感受到对于一个叶子节点深度齐平的子树来说，这个局部就只需要被修剪一次。
我们能否大胆得出结论：深度不同的叶子节点/子树对答案产生贡献。
是深度决定了时刻数，而在刚才的头脑风暴中我们知道了操作数可以在局部更改时刻数,所以深度差别的个数对操作数有贡献。
所以不同深度产生贡献是一定的，同深度不产生贡献也是一定的。
在此贴出赛时代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k;
struct tree{
	vector<int> chid;
}leaf[500010];
int ans=0;
int cnt=0;
void dfs1(int id,int fid,int deep){
	cnt=max(cnt,deep);
	for(int i=0;i<leaf[id].chid.size();i++){
		if(leaf[id].chid[i]!=fid){
			dfs1(leaf[id].chid[i],id,deep+1);
		}
	}
	return ;
}
int dfs2(int id,int fid,int deep){
	int j=0,o=k;
	vector<int> vec;
	int _max=0;
	for(int i=0;i<leaf[id].chid.size();i++){
		if(leaf[id].chid[i]!=fid){
			vec.push_back(dfs2(leaf[id].chid[i],id,deep+1));
			_max=max(_max,vec[vec.size()-1]);
			++j;
		}
	}
	if(j==0)return deep;
	for(int i=0;i<vec.size();i++)
		if(vec[i]==_max)o--;
	ans+=o;
	return _max;
}
signed main(){
	cin>>n>>k;
	if(k==1){
		cout<<n-1<<" "<<0;
		return 0;
	}
	for(int i=1,u,v;i<n;i++){
		cin>>u>>v;
		leaf[u].chid.push_back(v);
		leaf[v].chid.push_back(u);
	}
	dfs1(1,0,1);
	dfs2(1,0,1);
	cout<<cnt-1<<" "<<ans;
	return 0;
}
观察到赛时 20pts20pts 巨多，为了提供一个 2020 -> 100100 的思路并给出我个人的一些经验，于是献上此篇题解。

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...