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

题目：

简明题意：找将

T_{1}

变化成给出的

T_{2}

的时刻和最小操作数。

思路：

Part.1

很轻松的可以发现我们所求的时刻即为树的深度，在遍历树时我们可以得到。

Part.2

接下来我们来解决操作数，题目的条件就是两棵一样的树，由于我们可以随意编号且根节点确定，那么我们只需要处理树的形状。

一个贪心的想法是：将

T_{1}

长成

T_{2}

后删掉多余的子树的根节点。

可是细想一下上图的操作次数我们发现可以，按照上述贪心想法，图中树需进行两次删除操作，但实际上我们可以只删一次就达到要求。

问题就出现在我们可以在树生长过程中就进行删除操作，使树出现“参差不齐” 的形状来达到目标形状。

那么什么时候删除才最优呢？~~毋庸置疑~~是 $th_{now}-th_{v}$ 最优（

th_{i}

表示

Treeheight

, 即以 $i$ 为根节点的子树的高度。）。

代码实现时注意：

叶子结点 $th_{i}$ 为 0，不需要处理。
正常情况下删除节点 ans+=k。
当最优时刻时删会导致对于每一个需删节点对 $ans$ 的贡献减一。

最后附上代码。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
inline void read(int &a){
	char ch;int f=1,k=0;ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
	a=k*f;
}
struct edge{
	int start,end;
}e[N];
int head[N],cnt;
inline void add(int u,int v){
	e[++cnt].end=v;
	e[cnt].start=head[u];
	head[u]=cnt;
}
int n,k;
int fa[N],dep[N],vis[N],th[N],ans;
void dfs(int now,int fath){
	fa[now]=fath,dep[now]=dep[fath]+1;
	for(int i=head[now];i;i=e[i].start){
		int v=e[i].end;
		if(v==fath) continue;
		dfs(v,now);
		th[now]=max(th[now],th[v]+1);
	}
	if(!th[now]) return ;
	ans+=k;
	for(int i=head[now];i;i=e[i].start){
		int v=e[i].end;
		if(v==fath) continue;
		if(th[v]==th[now]-1) ans--;
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	read(n),read(k);
	for(int i=1;i<=n-1;i++){
		int u,v;
		read(u),read(v);
		add(u,v);add(v,u);
	}
	dfs(1,0);
	cout<<th[1]<<' '<<ans;
	return 0;
}

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

文章操作

题目：

思路：

Part.1

Part.2

Code

相关推荐

评论

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