hacker__man的博客

树的直径与LCA 无语了，我树的直径都能写错 树的直径大概有两种写法，树形dp和bfs。 树形dp：以1节点为根节点，考虑d[i]表示以i为根节点，从i走向i的子树的最远长度,显然d[i]可以用dfs,O(n)求解。 考虑f[i],表示经过i点的最长链的长度,maxf[1~n]就是树的直径，因为树的直径由四部分组成，又因为d[i]存储的是最大值，所以有很巧的方法可以一遍O(n)，求出d[i]，顺便求出树的直径。 int dp(int u,int fa) { for(int i=h[u];~i;i=

换根DP 换根dp一般的三步骤换根dp一般的三步骤换根dp一般的三步骤： 任意选择一个节点作为根 统计子树（自底向上）对每个根节点的贡献 （自顶向下）统计父节点对子节点的贡献并计算答案 Problem A:P3478 [POI2008]STA-Station // Problem: P3478 [POI2008]STA-Station // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P3478 // Memory Limit: 12

树的中心 树形dp,换根dp,必会题目，超级经典，奈何当初学的时候理解的不深入，还得重新理解树形dp,换根dp,必会题目，超级经典，奈何当初学的时候理解的不深入，还得重新理解树形dp,换根dp,必会题目，超级经典，奈何当初学的时候理解的不深入，还得重新理解 前置知识：树形dp求树的直径，换根dp换根dp可以把O(N2)的做法降低到O(N)的时间复杂度，力推！前置知识：树形dp求树的直径，换根dp\\ 换根dp可以把O(N^2)的做法降低到O(N)的时间复杂度，力推！前置知识：树形dp求树的直径，换根dp