首页 > 其他分享 >树上深度和问题 - 换根DP

树上深度和问题 - 换根DP

时间:2024-10-06 12:11:49浏览次数:7  
标签:sz dfs2 int fa DP ndp 树上 换根 dp

问题引出:

给出 \(n\) 个点的树,求出分别以不同的 \(i\) 为根时,所有结点深度的和,根节点的深度为 \(0\)。

首先我们有个自然的暴力思路, 也就是以每个节点为根节点做一遍 \(dfs\) 这样的复杂度是 \(O(n^2)\) 级别的, 所以要进行优化
看下图:

我们首先假设每个节点具有点权, 明显这里的点权是 \(1\), 接着给出以下定义:

  • 定义 \(c_i\) 为点权, 这里为 \(1\)
  • 定义 \(ALL\) 为所有点权的和
  • 定义 \(size_u\) 为以 \(u\) 为根的子树内的点权和
    假设我们此时以及求出了 \(0\) 号节点的答案 \(dp_0\), 那么当我们要求 \(2\) 号节点时, 我们把这个树分成两部分, 很明显黄框框出的部分内部的所有的节点到根节点的距离都要增加一个 \(w_{0 → 2}\), 这里明显边权为 \(1\), 那么其答案应该增加 \((ALL - size_2) * w_{0→2}\) , 接着看红框部分, 明显的所有的节点距离根节点的都要减去边权, 所以答案还应该减去 \(size_2 * w_{0→2}\), 故 \(dp_2 = dp_0 + ALL - size_2 - size_2\), 同理可以递推出其它的节点, 时间复杂度为 \(O(n)\)
    代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int n; cin >> n;
    
    int sum = 0;
    vector<int> c(n + 1);
    for(int i = 1; i <= n; i++) c[i] = 1, sum += c[i];

    vector<pair<int, int>> g[n + 1];
    for(int i = 1; i < n; i++){
        int a, b; cin >> a >> b;
        g[a].push_back({b, 1}), g[b].push_back({a, 1});
    }

    vector<int> dp(n + 1), sz(n + 1), dep(n + 1);
    function<void(int, int)> dfs1 = [&](int u, int fa) -> void{
        dp[1] += c[u] * dep[u], sz[u] = c[u];
        for(auto [x, y] : g[u]){
            if(x == fa) continue;
            dep[x] = dep[u] + y;
            dfs1(x, u);
            sz[u] += sz[x];     
        }
    };

    function<void(int, int, int)> dfs2 = [&](int u, int fa, int cur) -> void{
        dp[u] = cur;
        for(auto [x, y] : g[u]){
            if(x == fa) continue;
            int ndp = cur;
            ndp += (sum - sz[x]) * y - sz[x] * y;
            dfs2(x, u, ndp);
        }
    };

    dfs1(1, 0), dfs2(1, 0, dp[1]);

    for(int i = 1; i <= n; i++) cout << dp[i] << '\n';

    return 0;
}

变形题目

1. Minimize Sum of Distances

Minimize Sum of Distances
此时的点权就要变了, 但是其目的还是一样的, 按照我们的模板改一下点权就可以了, 此题还可以用重心来做, 直接求出重心也是可以的

重心代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int n; cin >> n;

    vector<int> g[n + 1];
    for(int i = 1; i < n; i++){
        int a, b; cin >> a >> b;
        g[a].push_back(b), g[b].push_back(a);
    }

    int sum = 0;
    vector<int> c(n + 1);
    for(int i = 1; i <= n; i++) cin >> c[i], sum += c[i];

    int res = 0, root = 0;
    vector<int> dp(n + 1), ndp(n + 1);
    dp[0]= 1e18;
    function<void(int, int)> dfs1 = [&](int u, int fa) -> void{
        dp[u] = 0, ndp[u] = c[u];
        for(auto x : g[u]){
            if(x == fa) continue;
            dfs1(x, u);
            ndp[u] += ndp[x];
            dp[u] = max(dp[u], ndp[x]);
        }
        dp[u] = max(dp[u], sum - ndp[u]);
        if(dp[u] < dp[root]) root = u;
    };

    function<void(int, int, int)> dfs2 = [&](int u, int fa, int d) -> void{
        for(auto x : g[u]){
            if(x == fa) continue;
            dfs2(x, u, d + 1);
            res += c[x] * d;
        }
    };

    dfs1(1, 0), dfs2(root, 0, 1);
    // for(int i = 1; i <= n; i++) cerr << dp[i] << ' ' << ndp[i] << endl;

    cout << res << '\n';

    return 0;
}

换根 \(dp\) 代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

    int n; cin >> n;
    
    vector<int> g[n + 1];
    for(int i = 1; i < n; i++){
        int a, b; cin >> a >> b;
        g[a].push_back(b), g[b].push_back(a);
    }

    int sum = 0;
    vector<int> c(n + 1);
    for(int i = 1; i <= n; i++) cin >> c[i], sum += c[i];

    vector<int> dp(n + 1), sz(n + 1);
    function<void(int, int, int)> dfs1 = [&](int u, int fa, int d) -> void{
        dp[1] += c[u] * d, sz[u] = c[u];
        for(auto x : g[u]){
            if(x == fa) continue;
            dfs1(x, u, d + 1);
            sz[u] += sz[x];     
        }
    };

    function<void(int, int, int)> dfs2 = [&](int u, int fa, int cur) -> void{
        dp[u] = cur;
        for(auto x : g[u]){
            if(x == fa) continue;
            int ndp = cur;
            ndp += sum - sz[x] * 2;
            dfs2(x, u, ndp);
        }
    };

    dfs1(1, 0, 0), dfs2(1, 0, dp[1]);

    cout << *min_element(dp.begin() + 1, dp.end()) << '\n';

    return 0;
}

下面的题只需要改改边权改改点权就可以了

2.[USACO10MAR] Great Cow Gathering G

[USACO10MAR] Great Cow Gathering G

3.Distance Sums 2

Distance Sums 2

4.Tree with Maximum Cost

Tree with Maximum Cost

5.[POI2008] STA-Station

[POI2008] STA-Station

6.Tree Painting

Tree Painting

7.「MXOI Round 1」城市

「MXOI Round 1」城市

标签:sz,dfs2,int,fa,DP,ndp,树上,换根,dp
From: https://www.cnblogs.com/o-Sakurajimamai-o/p/18448970

相关文章

  • NOIP 前 dp 做题小记
    NOIP前dp做题小记[BJOI2019]排兵布阵设\(f(i,j)\)表示在前\(i\)个城堡中总共派遣\(j\)个士兵时,可以获得的最大分数。初始化:\(\forall0\lej\lem\),\(f(0,j)=0\)答案统计:\(ans=f(n,m)\)转移:\(f(i,j)=\max_{0\lek\lej}f(i-1,j-k)+g(i,k)......
  • 斜率优化 DP
    斜率优化DP在单调队列优化过程中,转移方程被拆成了两部分,第一部分仅与\(j\)有关,而另一部分仅与\(i\)有关,因此我们可以利用单调队列仅维护与\(j\)有关的部分,实现问题的快速求解。但仍然有很多转移方程,\(i\)和\(j\)是紧密相关的,这个时候单调队列优化就不适用了,例如如下转......
  • DP 套 DP(DP of DP)
    把DP过程当作状态进行DP。DPofDP一般数据范围不会太大,而且一般是计数题。DPofDP的本质是自动机上DP。大致上可以写作\(dp[\dots][S]\)表示外层DP进行到\(\dots\)阶段,内层DP对应到\(S\)阶段。例一:基因题意:给出串\(s\)和一个数\(m\)。\(n=|s|\)。求对于......
  • TCPUDP 共用端口问题
    TCP/UDP共用端口问题。转载自:TCP/UDP占用端口问题总结-mengban-博客园(cnblogs.com)1.TCPUDP可以共同占用一个端口号吗?首先明确一点端口是一种抽象的软件结构(包括一些数据结构和I/O缓冲区)。应用程序(即进程)通过系统调用与某端口建立连接(binding)后,传输层传给该端口......
  • 基于DPAPI+RDP技术实现本地打开远程程序,并映射到本地机器桌面上
    本教程使用工具所使用的环境说明:启动器开发工具:VS2022启动器所用客户端技术:.NET8+WPF启动器其他技术:DPAPI启动器发布的可执行程序,系统要求:Windows7以及以上,X64如果需要本程序,可以在网盘获取。网盘地址:链接:https://pan.baidu.com/s/1QPstE5-1zPK-qOp8GQ90ew?pwd=6666......
  • CodeForces - 118D - dp
    这道题的思路可能来源于步兵后面必须跟骑兵,反之亦然,那么一个兵种当前的状态肯定是由另一个兵种上一个的状态推来的(即取用该当前取用的兵种之前)。接下来就要考虑怎么控制每次取用多少个人了,由题意可知,每次取用不得超过k1或k2,我们从1-n1和从1-n2表示骑兵和步兵当前的数量表示......
  • 树上最值路径 题解
    题意简述给你一棵\(n\)个结点的树,编号为\(1\simn\),求有多少路径\(\operatorname{Path}(u\rightarrowv)\),满足\(u=\max\{x\midx\in\operatorname{Path}(u\rightarrowv)\}\),\(v=\min\{x\midx\in\operatorname{Path}(u\rightarrowv)\}\)。......
  • 单调队列优化 DP
    单调队列可以\(O(n)\)求出子区间的最值,且顺序上要求区间的左端点和右端点单调不降。引入P1886滑动窗口/【模板】单调队列定义一个队列\(q\),我们让\(q\)中的元素满足单调不降。因此当\(x\)入队时,从前往后让不在当前范围的元素出队,从后往前将\(<x\)的元素全部出队,然......
  • 每日OJ题_牛客_DP2跳台阶_动态规划_C++_Java
    目录牛客_DP2跳台阶_动态规划题目解析C++代码Java代码牛客_DP2跳台阶_动态规划跳台阶_牛客题霸_牛客网题目解析        当前值只和数组的前两个值有关,在往前面的就无关了,所以没必要申请一个数组,直接使用两个变量即可,这样空间复杂度就满足要求了。C++代码......
  • WordPress文章发布技巧:让你的内容脱颖而出
    在当今的数字时代,内容是吸引和保持网站访问者注意力的关键。WordPress作为一个强大的内容管理系统,提供了多种工具和功能来帮助你优化文章发布过程。以下是一些技巧,可以帮助你更有效地发布WordPress文章,确保你的内容脱颖而出。优化标题标题是文章的第一个印象,它需要吸引人且包......