题解 [AGC004D] Teleporter

题目链接

躺在床上想到重要性质的题目。。。

首先，由于每个城市只有一个可以直接到达的城市，所以 \(n\) 个城市就有 \(n\) 条边，容易发现这是一棵基环树，那么我们先从普通树的角度考虑，若要求每个点走 \(k\) 条边恰好到 \(1\) 号节点，这个环必须加在哪里。

若 \(k=1\)，没有环显然也是可行的。

若 \(k=2\)，由于我们加的边是单向边，所以对于下面这种情况，唯一可以处理的方式就是在 \(1\) 那里连接自环，（注，从左往右图二和图三是错误的示范）：

那么，确定了唯一的环在一号节点，我们就可以在普通树上做了。

先思考从上往下贪心，对于深度 \(\ge k\) 的子树，将根节点提到 \(1\) 号节点的下面，但是这样显然是错的，反例如下：

容易发现，我们直接将 \(3\) 的子树提上去更优。

既然从上往下不行，我们考虑从下往上，由于两棵子树在这种情况下可能汇集到一个根节点，所以这样可以保证最优。

代码如下：

const int N=1e5+10;
int n,k,ans;
int a[N],dp[N];
vector<int> g[N];

void dfs(int nd,int fa) {
    for(int x:g[nd]) {
        dfs(x,nd);
        dp[nd]=max(dp[nd],dp[x]);
    }
    if(!fa) return ;
    dp[nd]++;
    if(dp[nd]==k&&fa!=1) {
        ans++;
        dp[nd]=0;
    }
}

int main() {
    n=read(); k=read();
    for(int i=1;i<=n;i++) {
        a[i]=read();
        if(i!=1) g[a[i]].push_back(i);
    }
    if(a[1]!=1) ans++;
    dfs(1,0);
    cout<<ans;

    return 0;
}