[动态规划] 树形DP

https://www.acwing.com/problem/content/1074/

由于是无向树，所以可以随意选择某个顶点作为根

以子树的根来作为划分依据，最长路径等于子树的最大路径长度和次最大路径长度之和

#include 
#include 
#include 

using namespace std;

const int N = 10010, M = 2 * N;

int n;
int h[N], e[M], w[M], ne[M], idx;
int ans;

inline int read(){
    int num = 0;
    char c;
    bool flag = false;
    while ((c = getchar()) == ' ' || c == 'n' || c == 'r');
    if (c == '-') flag = true;
    else num = c - '0';
    while (isdigit(c = getchar()))
    num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u, int fa) {
    int dist = 0;
    int d1 = 0, d2 = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        int d = dfs(j, u) + w[i];
        dist = max(d, dist);
        if (d >= d1) d2 = d1, d1 = d;
        else if (d > d2) d2 = d;
    }
    cout << dist << endl;
    ans = max(ans, d1+d2);
    return dist;
}

int main() {
    memset(h, -1, sizeof h);
    n = read();
    for (int i = 0; i < n-1; i ++) {
        int a, b, c;
        a = read();
        b = read();
        c = read();
        add(a, b, c), add(b, a, c);
    }
    dfs(5, -1);
    printf("%dn", ans);
    return 0;
}

https://www.acwing.com/problem/content/1075/

求某一点到树中其他结点的最远距离的最小值

对树的顶点按照上方和下方划分，对于某一个顶点而言，最远距离等于下方的最远距离和上方的最远距离取最大值

树的下方可按照上题方法来做，上方其实也是类似，做两遍 dfs

#include 
#include 
#include 

using namespace std;

const int N = 10010, M = 2 * N, INF = 0x3f3f3f3f;

int n;
int h[N], e[M], ne[M], w[M], idx;
int d1[N], d2[N], up[N], p1[N];
inline int read(){
    int num = 0;
    char c;
    bool flag = false;
    while ((c = getchar()) == ' ' || c == 'n' || c == 'r');
    if (c == '-') flag = true;
    else num = c - '0';
    while (isdigit(c = getchar()))
    num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int dfs_down(int u, int fa) {
    d1[u] = d2[u] = -INF;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        int d = dfs_down(j, u) + w[i];
        if (d >= d1[u]) {
            d2[u] = d1[u], d1[u] = d;
            p1[u] = j;
        }
        else if (d > d2[u]) d2[u] = d;
    }
    if (d1[u] == -INF) d1[u] = d2[u] = 0;
    if (d2[u] == -INF) d2[u] = 0;
    return d1[u];
}

void dfs_up(int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        if (j == p1[u]) {
            up[j] = max(d2[u], up[u]) + w[i];
        } else {
            up[j] = max(d1[u], up[u]) + w[i];
        }
        dfs_up(j, u);
    }
}

int main() {
    memset(h, -1, sizeof h);
    n = read();
    for (int i = 0; i < n-1; i ++) {
        int a, b, c;
        a = read(), b = read(), c = read();
        add(a, b, c), add(b, a, c);
    }
    dfs_down(1, -1);
    dfs_up(1, -1);
    int res = INF;
    for (int i = 1; i <= n; i ++) {
        res = min(res, max(d1[i], up[i]));
    }
    printf("%dn", res);
    return 0;
}

https://www.acwing.com/problem/content/1075/

求某一点到树中其他结点的最远距离的最小值

对树的顶点按照上方和下方划分，对于某一个顶点而言，最远距离等于下方的最远距离和上方的最远距离取最大值

树的下方可按照上题方法来做，上方其实也是类似，做两遍 dfs

#include 
#include 
#include 

using namespace std;

const int N = 10010, M = 2 * N, INF = 0x3f3f3f3f;

int n;
int h[N], e[M], ne[M], w[M], idx;
int d1[N], d2[N], up[N], p1[N];
inline int read(){
    int num = 0;
    char c;
    bool flag = false;
    while ((c = getchar()) == ' ' || c == 'n' || c == 'r');
    if (c == '-') flag = true;
    else num = c - '0';
    while (isdigit(c = getchar()))
    num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int dfs_down(int u, int fa) {
    d1[u] = d2[u] = -INF;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        int d = dfs_down(j, u) + w[i];
        if (d >= d1[u]) {
            d2[u] = d1[u], d1[u] = d;
            p1[u] = j;
        }
        else if (d > d2[u]) d2[u] = d;
    }
    if (d1[u] == -INF) d1[u] = d2[u] = 0;
    if (d2[u] == -INF) d2[u] = 0;
    return d1[u];
}

void dfs_up(int u, int fa) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa) continue;
        if (j == p1[u]) {
            up[j] = max(d2[u], up[u]) + w[i];
        } else {
            up[j] = max(d1[u], up[u]) + w[i];
        }
        dfs_up(j, u);
    }
}

int main() {
    memset(h, -1, sizeof h);
    n = read();
    for (int i = 0; i < n-1; i ++) {
        int a, b, c;
        a = read(), b = read(), c = read();
        add(a, b, c), add(b, a, c);
    }
    dfs_down(1, -1);
    dfs_up(1, -1);
    int res = INF;
    for (int i = 1; i <= n; i ++) {
        res = min(res, max(d1[i], up[i]));
    }
    printf("%dn", res);
    return 0;
}

https://www.acwing.com/problem/content/1077/

通过分析可得，每个数的 x x x 的约数之和 y y y 是固定的，也就是每个数只有唯一一个对应的约数之和，因此可以从 y y y 向 x x x 连一条有向边，利用这个性质可以按照这样的方式建树，无向边就转化为了有向边(当然无向边也是可以的，只不过需要多开两倍的数组空间)

本质上就是求树中的直径，权值为1

#include 
#include 
#include 

using namespace std;

const int N = 50010, M = N;

int n;
int sum[N];
int h[N], e[M], ne[M], idx;
bool st[N];
int res;
inline int read(){
    int num = 0;
    char c;
    bool flag = false;
    while ((c = getchar()) == ' ' || c == 'n' || c == 'r');
    if (c == '-') flag = true;
    else num = c - '0';
    while (isdigit(c = getchar()))
    num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u) {
    int d1 = 0, d2 = 0;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        int d = dfs(j) + 1;
        if (d >= d1) d2 = d1, d1 = d;
        else if (d > d2) d2 = d;
    }
    res = max(res, d1 + d2);
    return d1;
}

int main() {
    memset(h, -1, sizeof h);
    n = read();
    for (int i = 1; i <= n; i ++)
        for (int j = 2; j <= n / i; j ++)
            sum[i * j] += i;
    for (int i = 2; i <= n; i ++)
        if (i > sum[i])
            add(sum[i], i), st[i] = true;
    
    for (int i = 1; i <= n; i ++)
        if (!st[i]) dfs(i);
    printf("%dn", res);
    return 0;
}  

1. 在求约数时，利用试除法时间复杂度过高，为 O ( N N ) O(Nsqrt{N}) O(NN ​). 可以反过来考虑，对于每个数 d d d， 1 ∼ N 1sim N 1∼N 中以 d d d 为约数的数就是 d d d 的倍数， d , 2 d , 3 d , . . . , ⌊ N / d ⌋ ∗ d d, 2d, 3d, ..., lfloor N/d rfloor*d d,2d,3d,...,⌊N/d⌋∗d ，时间复杂度为 O ( N l o g N ) O(NlogN) O(NlogN)
2. 另外记录根结点，然后 dfs 时从根结点开始，因为生成的并不是完整的一棵树，而是森林，其中以 1 1 1 为根结点生成的树最大，而我们的答案就在其中。实测只 dfs(1) ， 也能 AC ，但并没有严谨的证明对于所有的数据都适用，最好还是遍历所有的树