HZNU-ACM寒假集训Day10小结树-树形DP

树形DP

加分二叉树洛谷P1040

注意中序遍历的特点：当根节点编号k时，编号小于k的都在其左子树上，编号大于k的都在右子树

转移方程 f[i,j]=max{f[i,k-1]*f[k+1,j]+d[k]} ,f[i,j]表示中序遍历i到j的二叉树最大加分时间复杂度O（N³）

#include<iostream>

#include<cstdio>

#include<string>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<cmath>

const double PI = acos(-1.0);

typedef long long ll;

using namespace std;

const int maxn = ;

int n, m;

int f[maxn][maxn], root[maxn][maxn], num[maxn];

void print(int l, int r) {         //先序遍历  根->左子树->右子树

    printf("%d ", root[l][r]);

    if (root[l][r] > l) print(l, root[l][r] - );

    if (root[l][r] < r) print(root[l][r] + , r);

}

int main() {

    scanf("%d", &n);

    for (int i = ; i <= n; i++) {

        scanf("%d", &num[i]);

        f[i][i] = num[i];

        root[i][i] = i;

        f[i][i - ] = f[i + ][i] = ;

    }

    for (int i = n; i >= ; i--) {

        for (int j = i + ; j <= n; j++) {

            for (int k = i; k <= j; k++) {

                if (f[i][k - ] * f[k + ][j] + f[k][k] <= f[i][j]) continue;

                f[i][j] = f[i][k - ] * f[k + ][j] + f[k][k];

                root[i][j] = k;

            }

        }

    }

    printf("%d\n", f[][n]);

    print(, n);

    return ;

}

P2015 二叉苹果树

#include<iostream>

#include<cstdio>

#include<string>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<cmath>

const double PI = acos(-1.0);

typedef long long ll;

using namespace std;

int n, cnt[], dp[][];

int q;

struct Edge {

    int w;

    int e;

}t;

vector<Edge> e[];

void dfs(int u, int p) {

    for (int i = ; i < e[u].size(); i++) {

        int v = e[u][i].e;

        if (v == p) continue;

        dfs(v, u);

        cnt[u] += cnt[v] + ;

        for (int j = min(cnt[u], q); j; j--) {

            for (int k = min(j - , cnt[v]); k >= ;)

                dp[u][j] = max(dp[u][j], dp[u][j - k - ] + dp[v][k] + e[u][i].w);

        }

    }

}

int main() {

    scanf("%d%d", &n, &q);

    for (int i = ; i < n; i++) {

        int x, y, w;

        scanf("%d%d%d", &x, &y, &w);

        t.e = y;

        t.w = w;

        e[x].push_back(t);

        t.e = x;

        e[y].push_back(t);

    }

    dfs(, );

    printf("%d", dp[][q]);

    return ;

}

洛谷P1352 没有上司的舞会

#include<iostream>

#include<cstdio>

#include<string>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<cmath>

const double PI = acos(-1.0);

typedef long long ll;

using namespace std;

const int maxn = ;

int w[maxn];

int v[maxn];

int f[maxn][];

vector<int> son[maxn];

void dfs(int x) {

    f[x][] = ;                   //初始化  f[x][0]表示以x为根的子树,且x不参加舞会的最大快乐值

    f[x][] = w[x];                //f[x][1]表示以x为根的子树，且x参加舞会的最大快乐值

    for (int i = ; i < son[x].size(); i++) {

        int y = son[x][i];

        dfs(y);

        f[x][] += max(f[y][], f[y][]);    //状态转移方程

        f[x][] += f[y][];

    }

}

int main() {

    int n;

    scanf("%d", &n);

    for (int i = ; i <= n; i++) scanf("%d", &w[i]);

    for (int i = ; i <= n - ; i++) {

        int x, y;

        scanf("%d%d", &x, &y);    //注意父亲在后

        son[y].push_back(x);

        v[x]++;

    }

    int root;

    for (int i = ; i <= n; i++) {

        if (!v[i]) {

            root = i;  break;

        }

    }

    dfs(root);

    printf("%d\n", max(f[root][], f[root][]));

    return ;

}

树上的常见操作

const int maxn = ;

vector<int> v[maxn];

int _size[maxn];    //结点大小

int mx_size[maxn];

int depth[maxn];

int Max[maxn];

int val[maxn];

void getsize(int x) {               //一棵N个点的无权树，问每个结点的大小

    _size[x] = ;

    for (int i = ; i < v[x].size(); i++) {

        getsize(v[x][i]);

        _size[x] += _size[v[x][i]];

    }

}

void getdep(int x) {                //一棵N个点的无权树，问每个结点的深度

    for (int i = ; i < v[x].size(); i++) {

        depth[v[x][i]] = depth[x] + ;

        getdep(v[x][i]);           //自顶向下

    }

}

void getmax(int x) {             //一棵N个点的点权树，问每个子树的点权和，点权最大值

    Max[x] = val[x];

    for (int i = ; i < v[x].size(); i++) {

        getmax(v[x][i]);

        Max[x] = max(Max[x], Max[v[x][i]]);

    }

}

求树的重心

定义：找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡

C++代码

#include<iostream>

#include<cstdio>

#include<string>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#include<cmath>

const double PI = acos(-1.0);

#define INF 0x3f3f3f3f

typedef long long ll;

using namespace std;

const int maxn = ;

int n, m, ans;

int len, lenp;

int _size[maxn], id[maxn], p[maxn];

vector<int> e[maxn];

bool vis[maxn];

int dfs(int x) {

    if (!e[x].size()) return ;

    int sum = ;

    for (int i = ; i < e[x].size(); i++) {

        if (!vis[e[x][i]]) {

            vis[e[x][i]] = true;

            sum += dfs(e[x][i]);

        }

    }

    return sum;

}

int main() {

    scanf("%d", &n);

    int x, y;

    for (int i = ; i < n; i++) {

        scanf("%d%d", &x, &y);

        e[x].push_back(y);

    }

    for (int i = ; i <= n; i++) {

        memset(vis, , sizeof vis);

        vis[i] = ;

        _size[i] = dfs(i);

    }

    int Min = INF;

    for (int i = ; i <= n; i++) {

        int Max = n - _size[i];

        for (int j = ; j < e[i].size(); j++) Max = max(Max, _size[e[i][j]]);

        Min = min(Max, Min);

        p[i] = Max;

    }

    for (int i = ; i <= n; i++) {

        if (p[i] == Min) {

            lenp++;

            id[lenp] = i;

        }

    }

    printf("%d\n", lenp);             //重心个数

    for (int i = ; i <= lenp; i++) printf("%d\n", id[i]);

    return ;

}

巴特西

HZNU-ACM寒假集训Day10小结树-树形DP

最新文章

热门文章

巴特西

HZNU-ACM寒假集训Day10小结 树-树形DP

最新文章

热门文章

HZNU-ACM寒假集训Day10小结树-树形DP