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

chenyizhen · 2025-07-20 16:36:21 · 题解

题目：

简明题意：找将 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

#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;
}