题解：P9369 [ICPC2022 Xi'an R] Tree

· · 题解

先来转化一下所给条件。

先看第一个条件，意味着这个集合的点处在同一条链上。

再看第二个条件，意味着这个集合处在不同的链上，处在同一深度。

那么我们将树进行长链剖分，那么假设将长度在前 x 的链当作第一个集合，那么后面的点要么是也是第一个集合，要么是第二个集合，而第二个集合的数量应是剩下链中的长度最大值，假设我们不按照长度一个一个选链，而是跳着选，那么这种一定不会是最优的，你可以手玩几组数据就知道了。于是我们可以进行枚举所选的链，然后再统计答案即可。

有一个坑点，就是别拿邻接表存图，因为多测清空邻接表复杂度有点很高，会 TLE。其他就没了。

Code

#include <bits/stdc++.h>
using namespace std ;
const int MAXN = 1e6 + 10 ;
struct edge {
    int to, nxt ;
}e[MAXN] ;
int head[MAXN] ;
int len[MAXN], son[MAXN], siz[MAXN], tot ;
inline int read() {
    register int x = 0, f = 0;
    register char ch = getchar();
    while (ch < '0' || ch > '9')
        f |= ch == '-', ch = getchar();
    while (ch >= '0' && ch <= '9')
        x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    return f ? -x : x;
}
inline void add (int u, int v) {
    e[++tot].to = v ;
    e[tot].nxt = head[u] ;
    head[u] = tot ;
}
inline bool cmp (int x, int y) {
    return x > y ;
}
inline void dfs (int x) {
    for (int i = head[x] ; i ; i = e[i].nxt) {
       int v = e[i].to ;
       dfs(v) ;
       if (siz[son[x]] < siz[v]) son[x] = v ;
    }
    siz[x] = siz[son[x]] + 1 ;
}
inline void redfs (int x, int k) {
    if (!son[x]) len[++tot] = k ;
    else redfs(son[x], k + 1) ;
    for (int i = head[x] ; i ; i = e[i].nxt) {
        int v = e[i].to ;
        if (v != son[x]) redfs (v, 1) ;
    }
}
int main () {
    int t ;
    t = read() ;
    while (t--) {
        int n ;
        n = read() ;
        int x ;
        for (int i = 1 ; i <= n ; i++) head[i] = 0, son[i] = 0 ;
        tot = 0 ;
        for (int i = 2 ; i <= n ; i++) {
            x = read() ;
            add(x, i) ;
        }
        tot = 0 ;
        dfs(1) ;
        redfs(1, 1) ;
        sort(len + 1, len + tot + 1, cmp) ;
        int ans = len[1] ;
        len[tot + 1] = 0 ;
        for (int i = 1 ; i <= tot ; i++) ans = min(i + len[i + 1], ans) ;
        cout << ans << '\n' ;
    }
}