例题

A.树上求和 or 285. 没有上司的舞会

也可以看我自己写的题解

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 6060;

int n, w[N];
int f[N][2];
int e[N], ne[N], h[N], idx;
bool st[N];

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

void dfs(int x)
{
    f[x][1] = w[x];

    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        dfs(j);

        f[x][0] += max(f[j][0], f[j][1]); // 当前节点如果不选,那么子节点可以选也可以不选
        f[x][1] += f[j][0]; // 当前节点选,那么子节点只能不选
    }
}

int main()
{
    memset(h, -1, sizeof h);
    scanf ("%d", &n);

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

    for (int i = 1; i < n; i ++)
    {
        int a, b;
        scanf ("%d %d", &a, &b);
        st[a] = true;
        add(b, a);
    }

    int root = 1;
    while (st[root]) root ++;

    dfs(root);

    printf ("%d", max(f[root][0], f[root][1]));
    return 0;
}

B.结点覆盖

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15005;

int n;
int h[N] ,cnt;
int f[N][3]; // f[i][0 / 1 / 2]分别表示选择 i 的父节点 / 子节点 / 本身 的最小花费
bool vis[N];
int k[N];

struct node
{
    int to ,ne;
}e[N];

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

void dfs(int x,int fa)
{
    int d = 0x3f3f3f3f;

    for (int i = h[x]; i; i = e[i].ne)
    {
        int v = e[i].to;

        if (v == fa) continue;

        dfs(v , x);

        f[x][0] += min(f[v][1] , f[v][2]); // 如果选择了 x 父节点,则 y 只能被其子节点或本身覆盖
        f[x][1] += min(f[v][1] , f[v][2]); // 如果选择了 x 的子节点,则至少有一个子节点被选了
        d = min(d , f[v][2] - min(f[v][1] , f[v][2]));
         // 这里是保证了至少有一个子节点被选,因为如果 d 还未被更新的值是正无穷
         //如果 f[x][1] 在上一行被加上了f[v][2],那么 d 就被更新成了 0
         //则就保证了一定有一个子节点的f[v][2](就是子节点自身被选)被加入到f[x][1](太妙了)
        f[x][2] += min(f[v][0] , min(f[v][1] , f[v][2])); // 如果 x 选自身 , 那么子节点三种情况都有可能
    }

    f[x][1] += d; // 保证一定有一个子节点被选
    f[x][2] += k[x]; // 选择自身,就把自身的价值加上
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int a ,b ,c ,d;
        cin >> a >> b >> c;
        k[a] = b;
        while (c --)
        {
            cin >> d;
            add(a , d);
            vis[d] = true;
        }
    }
    // 因为你不知道根节点是哪个,还得找
    int root = 1;
    while (vis[root]) root ++;

    dfs(root , 0);

    printf ("%d",min(f[root][1] , f[root][2])); // 因为根节点没有父亲,只能是选子节点和自身两种情况
    return 0;
}

C.最长距离

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;

int n;
int h[N] ,cnt;
int mmax[N] ,cmax[N];

struct node
{
    int to ,ne ,w;
}e[N];

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

void dfs(int x,int fa)
{
    mmax[x] = 0;
    cmax[x] = 0;
    for (int i = h[x]; i; i = e[i].ne)
    {
        int v = e[i].to,w = e[i].w;
        if (v == fa) continue;
        dfs(v , x);

        if (mmax[v] + w > mmax[x])
        {
            cmax[x] = mmax[x];
            mmax[x] = mmax[v] + w;
        }
        else if (mmax[v] + w > cmax[x]) cmax[x] = mmax[v] + w;
    }
}

void udfs(int x,int fa,int w)
{
    if (mmax[fa] != mmax[x] + w) // 如果这个节点到它的父亲节点的距离 不是 它的父亲节点到所以子节点的距离的最大值,则可以用最大值更新
    {
        if (mmax[x] < mmax[fa] + w)
        {
            cmax[x] = mmax[x];
            mmax[x] = mmax[fa] + w;
        }
        else if (mmax[fa] + w > cmax[x]) cmax[x] = mmax[fa] + w;
    }
    else // // 如果这个节点到它的父亲节点的距离 是 它的父亲节点到所以子节点的距离的最大值,则要用次大值更新,因为如果用最大值就往上走一次又往下走了一次
    {
        if (mmax[x] < cmax[fa] + w)
        {
            cmax[x] = mmax[x];
            mmax[x] = cmax[fa] + w;
        }
        else if (cmax[fa] + w > cmax[x]) cmax[x] = cmax[fa] + w;
    }

    for (int i = h[x]; i ; i = e[i].ne)
    {
        int v = e[i].to;
        if (v == fa) continue;
        udfs(v , x , e[i].w);
    }
}

int main()
{
    while(scanf("%d",&n) != EOF)
    {
        cnt = 0;
        memset(h , 0 , sizeof h);
        for (int i = 2; i <= n; i++)
        {
            int a ,b;
            cin >> a >> b;
            add(a , i , b);
        }

        dfs(1 , 0);

        for (int i = h[1]; i; i = e[i].ne)
            udfs(e[i].to , 1 , e[i].w);

        for (int i = 1; i <= n; i++) printf ("%d\n",mmax[i]);
    }
}

D.选课方案

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 303;

int n ,m;
int k[N];
int h[N] ,cnt;
int f[N][N];

struct node
{
    int to ,ne;
}e[N];

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

void dfs(int x)
{
    f[x][0] = 0;
    for (int i = h[x]; i; i = e[i].ne)
    {
        int v = e[i].to;
        dfs(v);

        // 做一次背包
        for (int j = m; j >= 0; j--)
            for (int use = j; use >= 0; use--) // 枚举在 v 这个子节点上选几门课程
                f[x][j] = max(f[x][j] , f[x][j - use] + f[v][use]);
    }
    if (x)
    {
        for (int i = m; i > 0; i--)
            f[x][i] = f[x][i - 1] + k[x];
    }
}

int main()
{
    cin >> n >> m;
    // 因为有多棵树 , 所以我们可以建立一个超级源点 0 
    for (int i = 1; i <= n ; i++)
    {
        int a;
        cin >> a >> k[i];
        add(a , i);
    }

    dfs(0);

    printf ("%d",f[0][m]);

    return 0;
}

E.路径求和

一条边把图分成了A 和 B 两部分,那这条边被计算的次数就等于 A的叶节点个数与B节点数的乘积，加上B的叶节点个数与A节点数的乘积

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1010000;

int n ,m;
int h[N];
int d[N];
LL le[N] ,nod[N] ,num ,cnt;
int id[N] ,nu;
bool vis[N];
LL res;

struct node
{
    int to ,ne ,w;
}e[N];

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

void dfs(int x,int fa)
{
    nod[x] = 1;
    if (d[x] == 1) num ++,le[x] = 1; 

    for (int i = h[x]; ~i; i = e[i].ne)
    {
        int v = e[i].to;
        if (v == fa) continue;
        dfs(v , x);

        nod[x] += nod[v];
        le[x] += le[v];
    }
}

void query(int x,int fa)
{
    for (int i = h[x]; ~i; i = e[i].ne)
    {

        int v = e[i].to,w = e[i].w;
        if (v == fa) continue;
        query(v , x);
        res += (LL) w  * (nod[v] * (num - le[v]) + le[v] * (n - nod[v]));

    }
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a ,b ,c;
        cin >> a >> b >> c;
        if (!vis[b]) id[++ nu] = b,vis[b] = true;
        if (!vis[c]) id[++ nu] = c,vis[c] = true;
        add(b , c , a);
        add(c , b , a);
        d[b] ++ , d[c] ++;
    }

    dfs(id[1] , 0);

    query(id[1] , 0);
    printf ("%lld",res);

    return 0;
}

F.树上移动

这题和上面的C题很像

答案一：求最大路径,再用总权值之和的两倍 - 最大路径
答案二：求最大链(以 u 为根节点的树到子节点的最大路径和次大路径相加),再用总权值之和减去最大链的长度

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long LL;

const int N = 10000010;

int n ,S;
int h[N] ,cnt;
LL f1[N] ,f2[N];
bool vis[N];
LL num;
struct node
{
    int to ,ne ,w;
}e[N];

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

void dfs(int x,int fa)
{
    f1[x] = 0,f2[x] = 0;
    for (int i = h[x]; i; i = e[i].ne)
    {
        int v = e[i].to,w = e[i].w;
        if (v == fa) continue;

        dfs(v , x);

        if (f1[x] < f1[v] + w)
        {
            f2[x] = f1[x];
            f1[x] = f1[v] + w;
        }
        else if (f2[x] < f1[v] + w) f2[x] = f1[v] + w;
    }
}

int main()
{
    cin >> n >> S;
    for (int i = 1; i < n; i++)
    {
        int a ,b ,c;
        cin >> a >> b >> c;
        add(a , b , c);
        add(b , a , c);
        num += 1ll * c * 2;
    }

    dfs(S , 0);

    LL res1 = 0,res2 = 0;
    for (int i = 1; i <= n; i++)
    {
        res1 = max(res1 , f1[i]);
        res2 = max(res2 , f1[i] + f2[i]);
    }

    printf("%lld\n%lld",num - res1,num - res2);
    return 0;
}