首页 > 其他分享 >换根 DP

换根 DP

时间:2024-11-09 08:47:22浏览次数:3  
标签:pre cur int tree 换根 ans 节点 DP

树形 DP 中的换根 DP 问题又被称为二次扫描,通常需要求以每个点为根时某个式子的答案。

这一类问题通常需要遍历两次树,第一次遍历先求出以某个点(如 \(1\))为根时的答案,在第二次遍历时考虑由根为 \(u\) 转化为根为 \(v\) 时答案的变化(换根)。这个变化往往分为两部分,\(v\) 子树外的点到 \(v\) 相比于到 \(u\) 会增加一条边,而 \(v\) 子树内的点到 \(v\) 相比于到 \(u\) 会减少一条边。

所以往往在第一次遍历时可以顺带求出一些子树信息,利用这些信息辅助第二次遍历时的换根操作。

经典例题:求对于每个点而言,其他点到这个点的距离之和。

例题:P3478 [POI2008] STA-Station

给定一棵 \(n\) 个节点的树,求出一个节点,使得以这个节点为根时,所有节点的深度之和最大。
数据范围:\(n \le 10^6\)。

分析:随便选择一个节点 \(u\) 作为根节点,遍历整棵树,则得到了以 \(u\) 为根节点时的深度之和。

令 \(dp_u\) 表示以 \(u\) 为根时,所有节点的深度之和。设 \(v\) 为当前节点的某个子节点,考虑“换根”,即以 \(u\) 为根转移到以 \(v\) 为根,显然在换根的过程中,以 \(v\) 为根会导致每个节点的深度都产生改变。具体表现为:

  • 所有在 \(v\) 的子树上的节点深度都减少了一,那么总深度和就减少了 \(sz_v\),这里用 \(sz_i\) 表示以 \(i\) 为根的子树中的节点个数。
  • 所有不在 \(v\) 的子树上的节点深度都增加了一,那么总深度和就增加了 \(n - sz_v\)。

根据这两个条件就可以推出状态转移方程:\(dp_v = dp_u + n - 2 \times sz_v\),因此可以在第一次遍历时顺便计算一下 \(sz\),第二次遍历时用状态转移方程计算出最终的答案。

参考代码
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1000005;
vector<int> tree[N];
int sz[N], res, n;
LL ans;
void dfs(int cur, int fa, int depth) {
    ans += depth;
    sz[cur] = 1;
    for (int to : tree[cur]) {
        if (to == fa) continue;
        dfs(to, cur, depth + 1);
        sz[cur] += sz[to];
    }
}
void solve(int cur, int fa, LL sum) {
    for (int to : tree[cur]) {
        if (to == fa) continue;
        LL tmp = sum + n - 2 * sz[to];
        if (tmp > ans) {
            ans = tmp; res = to;
        }
        solve(to, cur, tmp);
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        tree[u].push_back(v); tree[v].push_back(u);
    }
    dfs(1, 0, 1);
    res = 1;
    solve(1, 0, ans);
    printf("%d\n", res);
    return 0;
}

习题:P2986 [USACO10MAR] Great Cow Gathering G

解题思路

与上一题类似,只不过这题换根时的变化量是点权和(即牛棚中奶牛的数量)的变化乘以边权。

参考代码
#include <cstdio>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 100005;
int n, c[N];
LL ans;
struct Edge {
    int to, l;
};
vector<Edge> tree[N];
void dfs(int cur, int fa, int depth) {
    ans += 1ll * depth * c[cur];
    for (Edge e : tree[cur]) {
        if (e.to == fa) continue;
        dfs(e.to, cur, depth + e.l);
        c[cur] += c[e.to];
    }
}
void solve(int cur, int fa, LL sum) {
    for (Edge e : tree[cur]) {
        if (e.to == fa) continue;
        LL tmp = sum + 1ll * (c[1] - 2 * c[e.to]) * e.l;
        ans = min(ans, tmp);
        solve(e.to, cur, tmp);
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
    for (int i = 1; i < n; i++) {
        int a, b, l; scanf("%d%d%d", &a, &b, &l);
        tree[a].push_back({b, l}); tree[b].push_back({a, l});
    }
    dfs(1, 0, 0);
    solve(1, 0, ans);
    printf("%lld\n", ans);
    return 0;
}

例题:P3047 [USACO12FEB] Nearby Cows G

分析:可以先对树做一次遍历得到每个节点对应的子树下距离子树根节点距离 \(0 \sim x\) 之间的点权和,

然后考虑每个点距离 \(k\) 之内的点权和。子树下的点权和在第一次遍历时已经计算完成,因此还需要计算的是在该点子树外的距离 \(k\) 以内的部分,而这个部分可以通过对该点上方最多 \(k\) 个祖先节点的处理,如下图所示。

image

参考代码
#include <cstdio>
#include <vector>
using std::vector;
const int N = 100005;
const int K = 25;
vector<int> tree[N];
int n, k, sum[N][K], c[N], ans[N];
void dfs(int u, int fa) {
    for (int v : tree[u]) {
        if (v == fa) continue;
        dfs(v, u);
        for (int i = 1; i <= k; i++) {
            sum[u][i] += sum[v][i - 1];
        }
    }
    sum[u][0] = c[u];
}
void calc(int u, int fa, vector<int> pre) {
    int dis = pre.size();
    pre.push_back(u);
    // u的子树内的距离范围内的点权和
    ans[u] = sum[u][k];
    // 计算u的子树外的距离范围内的点权和
    for (int i = 0; i + 1 < pre.size(); i++) {
        int cur = pre[i], nxt = pre[i + 1];
        // 对于边cur->nxt
        ans[u] += sum[cur][k - dis]; // 加上cur子树下的距离内点权和
        if (k - dis > 0) ans[u] -= sum[nxt][k - dis - 1]; // 减去nxt子树下刚刚被重复计算的部分
        dis--;
    }
    vector<int> path;
    if (pre.size() == k + 1) {
        // pre[0]即将超出下面的点的距离范围k,要被淘汰
        for (int i = 1; i < pre.size(); i++) path.push_back(pre[i]);
    } else path = pre;
    for (int v : tree[u]) {
        if (v == fa) continue;
        calc(v, u, path);
    }
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        tree[u].push_back(v); tree[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
    dfs(1, 0);
    // 生成前缀和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) sum[i][j] += sum[i][j - 1];
    }
    vector<int> tmp;
    calc(1, 0, tmp);
    for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
    return 0;
}

标签:pre,cur,int,tree,换根,ans,节点,DP
From: https://www.cnblogs.com/ronchen/p/18536275

相关文章

  • 第一天打卡,udp协议
    今天学了udp协议基础,udp协议是一种无连接的网络协议,提供一种简单的方式来输送数据。发送:要用到的方法封装在InetAddress类中,其中DatagramSocket对象ds相当于快递员身份,不传递参数值的话会随机生成端口,进行输送快递(数据),快递的身份由DatagrampPacket对象充当,把东西打包。其中的......
  • [At_dp_w] Intervals & [At_dp_x] Tower
    两道题都很好Intervals给定\(m\)条规则形如\((l_i,r_i,a_i)\)​,对于一个01串,其分数的定义是:对于第\(i\)条规则,若该串在\([l_i,r_i]\)中至少有一个1,则该串的分数增加\(a_i\)你需要求出长度为\(n\)的01串中的最大分数\(1\len,m\le2\times10^5,|a_i|\le10^9\)......
  • Leetcode 474 dp数组讲解和滚动数组优化
    474.一和零​ ​dp[i][w1][w2]:DP数组的集合:考虑前i个物品包括第i个,满足背包重量不超过[w1][w2]的所有集合把输入数组中的每个string当作是一个物品,其重量分别为string中0和1的个数属性:价值每个物品的价值是1因为我们求最大子集的个数,一个字符串对子集个数贡献的......
  • 插入类DP
    对于这类题目的特征:1.排列性质2.\(100\len\le5\times10^3\)3.答案和排列的上升下降的突变点有关套路:按照某个从小到大的顺序插入,有了这个顺序就能算贡献或者方案数贡献往往提前计算,存在每个元素有新开一段、合并两端、连在某一段后面的不同方案有的允许了\(A\),\(W\),\(......
  • 大模型--训练 加速之 数据并行(DP, DDP与ZeRO)-上-12
    目录1.参考2.总结3.分布式数据并行(DDP)4.总结1.参考https://zhuanlan.zhihu.com/p/6171339712.总结以GoogleGPipe为代表的流水线并行范式,当模型太大,一块GPU放不下时,流水线并行,将模型的不同层放到不同的GPU上,通过切割mini-batch实现对训练数据的流水线处理,提升GPU计算......
  • 知识分享:Air780E软件之UDP应用示例
    一、UDP概述UDP(用户数据报协议,UserDatagramProtocol)是一种无连接的、不可靠的传输层协议,主要用于实现网络中的快速通讯。以下是UDP通讯的主要特点:1.1无连接通讯:UDP在发送数据之前不需要建立连接,这大大减少了通讯的延迟。发送方只需将数据包封装成UDP报文,并附上目的地址......
  • 洛谷 P2113 看球泡妹子(DP)
    传送门https://www.luogu.com.cn/problem/P2113解题思路可以设  表示前  场比赛看了  场,小红的满足度为  的最大精彩度。然后可以枚举前面的一个比赛 ,可以得到转移方程:但是,我们发现数组空间有一点小大,可以优化一下。发现每一次转移都是 ,于是可以滚动数组优化空......
  • P10161 [DTCPC 2024] 小方的疑惑 10 [构造 + 背包DP]
    P10161[DTCPC2024]小方的疑惑10Solution一开始看这题的时候,我们可能会觉得无从下手,这时不妨列出几种方案,计算它们的贡献,尝试得到一些启发。画来画去,发现无非就是并列和包含两种情况,并列就是()()()(),设它一共由\(x\)对括号组成,那么它的总贡献是\(x\times(x+1)\div......
  • 面试:TCP、UDP如何解决丢包问题
    文章目录一、TCP丢包原因、解决办法1.1TCP为什么会丢包1.2TCP传输协议如何解决丢包问题1.3其他丢包情况(拓展)1.4补充1.4.1TCP端口号1.4.2多个TCP请求的逻辑1.4.3处理大量TCP连接请求的方法1.4.4总结二、UDP丢包2.1UDP协议2.1.1UDP简介2.1.2......
  • 一类树形 dp
    省流:设计dp状态及转移,利用转移在链上复杂度低的特点或单独设计在链上的转移方式(并且这类dp合并的复杂度一般与子树大小有关),使得最劣情况相当于一棵满二叉树,得到较为优秀的复杂度。例题1给定一棵树,在树上选出一些点,使所有从根到叶子结点的路径上选出的点的个数相同。求方案......