题解：P11978 [KTSC 2021] 铁路 / railroad

· · 题解

前情提要：更好的阅读体验。

题意

题目给出一颗 N 个点的树，要求设计一种方案，在上面添加 K 条边（要求原本不相连），可以将一个点标记，并且将全部点重新编号；然后在这个新图中以之前的信息复原出原树，即删除全部添加的边。

分析

首先，如果重新编号所有点变成图的话我们就无法确认原来的根、叶子之类的节点，所以我们考虑先把所有 K 条边的一端都接在同一个节点上，我们称该节点为“总节点”。但如果直接标记该节点会发现我们无法得知与该点相连的是原来的树还是新加的边。我们尝试以别的方式确认那个点。

我们发现，如果我们把总节点放在一个叶子节点，那么该点相连的边有 K + 1 条，会比较好确认，因为叶子节点是树中相连边最少的点。那么我们标记叶子节点的父亲节点，不仅同时确认总节点的位置也确认哪个是原树边，会是一个比较好的方案。

但其实还有个问题，如果还有一个与标记节点直接相连的点原本也连接了 K + 1 条边的话，我们怎么确认哪个是真的叶子节点呢？考虑以下情况：

还有一个小的误区：对于 K = 1 的情况，如果总节点连接了与其同父亲的另一个节点，那么两者相连边数量一致，如何判断哪个是总节点呢？其实不用判断啊，反正 K = 1，只要找出相连的一条新边即可。

AC code

#include<bits/stdc++.h>
#include<utility>
using namespace std;
typedef int ll;
typedef pair<ll,ll> pir;
const int N=304;
ll rt,id,tid,mdep,d[N];
ll tot,head[N];
struct Edge{
    ll to,nxt;
}e[N<<1];
void add_edge(ll u,ll v){
    e[++tot].to=v;
    e[tot].nxt=head[u];
    head[u]=tot;
}
void init(){
    for(int i=1;i<=tot;i++){
        e[i].to=e[i].nxt=0;
    }
    rt=id=tid=mdep=tot=0;
    memset(head,0,sizeof(head));
    memset(d,0,sizeof(d));
}
void dfs(ll u,ll fa,ll dep){
    bool flag=true;
    for(int i=head[u];i;i=e[i].nxt){
        ll v=e[i].to;
        if(v==fa){
            d[u]++;
            continue;
        }
        dfs(v,u,dep+1);
        flag=false;
        d[u]++;
    }
    if(flag&&dep>mdep){
        id=u;
        rt=fa;
        mdep=dep;
    }
}
vector<pir> encode_map(ll N,ll K,ll &X,vector<pir> E){
    init();
    for(int i=0;i<E.size();i++){
        add_edge(E[i].first,E[i].second);
        add_edge(E[i].second,E[i].first);
    }
    dfs(1,0,1);
    vector<pir> ans;
    X=rt;
    for(int i=head[rt];i;i=e[i].nxt){
        ll v=e[i].to;
        if(d[v]!=1){
            if(d[v]-1==K){
                ans.push_back(make_pair(v,id));
            }
            tid=v;
        }
    }
    for(int i=1;ans.size()<K;i++){
        if(i!=rt&&i!=id&&i!=tid){
            ans.push_back(make_pair(id,i));
        }
    }
    return ans;
}
vector<pir> decode_map(ll N,ll K,ll X,vector<pir> E){
    init();
    for(int i=0;i<E.size();i++){
        add_edge(E[i].first,E[i].second);
        add_edge(E[i].second,E[i].first);
    }
    for(int i=head[X];i;i=e[i].nxt){
        ll v=e[i].to;
        for(int j=head[v];j;j=e[j].nxt){
            d[v]++;
        }
        if(d[v]-1==K){
            id=v;
        }
    }
    vector<pir> ans;
    for(int i=0;i<E.size();i++){
        if(E[i].first==id||E[i].second==id){
            if(E[i].first!=X&&E[i].second!=X){
                continue;
            }
        }
        ans.push_back(make_pair(E[i].first,E[i].second));
    }
    return ans;
}

一些易错点：