树形DP之换根学习笔记 & 消息传递(news)题解

代码

#include<cstdio>
#include<algorithm>
using namespace std;

const int N = 200000;
int f[N + 5] , g[N + 5] , h[N + 5] , son[N + 5] , res[N + 5] , Maxl[N + 5] , Maxr[N + 5];
int tot = 1 , cnt , n , F , ans;
struct edge{
    int to , nxt;
}e[N + 5];

inline void add(int x , int y) {e[++tot].to = y , e[tot].nxt = h[x] , h[x] = tot;}
inline int o(int x){return x == F ? g[x] : f[x];}
inline bool cmp(int x , int y) {return o(x) > o(y);}

inline void getf(int u)
{
    for(register int i = h[u]; i; i = e[i].nxt) getf(e[i].to);
    cnt = F = 0;
    for(register int i = h[u]; i; i = e[i].nxt) son[++cnt] = e[i].to;
    sort(son + 1 , son + cnt + 1 , cmp);
    for(register int i = 1; i <= cnt; i++) f[u] = max(f[u] , f[son[i]] + i);
}

inline void getg(int u)
{
    if (u > 1) son[cnt = 1] = F = u;
    else cnt = F = 0;
    for(register int i = h[u]; i; i = e[i].nxt) son[++cnt] = e[i].to;
    sort(son + 1 , son + cnt + 1 , cmp);
    
    Maxl[0] = Maxr[cnt + 1] = 0;
    for(register int i = 1; i <= cnt; i++) Maxl[i] = max(Maxl[i - 1] , o(son[i]) + i);
    for(register int i = cnt; i >= 1; i--) Maxr[i] = max(Maxr[i + 1] , o(son[i]) + i);
    
    for(register int i = 1; i <= cnt; i++)
    {
        if (son[i] == u) continue;
        g[son[i]] = max(Maxl[i - 1] , Maxr[i + 1] - 1);
    }
    res[u] = Maxl[cnt];
    for(register int i = h[u]; i; i = e[i].nxt) getg(e[i].to);
}

inline int read()
{
    char ch = getchar();
    int x = 0;
    for(; ch < '0' || ch > '9'; ch = getchar());
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
    return x;
}

int main()
{
    freopen("news.in" , "r" , stdin);
    freopen("news.out" , "w" , stdout);
    n = read();
    int fa;
    for(register int i = 2; i <= n; i++) fa = read() , add(fa , i);
    getf(1) , getg(1);
    ans = 2e9;
    for(register int i = 1; i <= n; i++) ans = min(res[i] , ans);
    printf("%d\n" , ans + 1);
    for(register int i = 1; i <= n; i++) 
    if (res[i] == ans) printf("%d " , i);
}

树形DP之换根学习笔记 & 消息传递(news)题解

原文：https://www.cnblogs.com/leiyuanze/p/12319169.html