百度之星 Diversity （简单树形dp）-北京尧图网络

题意描述Diversity给你一棵n个点的树对于节点ii你要给它标上一个[li,ri]之间的数要求所有边两端节点上标的数字的差的绝对值的总和最大。Input第一行一个整数T T(1≤T≤5)表示数据组数。对于每组数据格式如下。第一行一个正整数n(2≤n≤105)。接下来n-1行每行两个正整数 u, v(1≤u,v≤n)表示一条边。接下来nn行第ii行两个正整数li,ri(1 ≤ li ≤ ri ≤ 10^9)。Output对于每组数据一个整数表示答案。Sample Input1 5 1 2 2 3 3 4 4 5 1 5 2 7 7 9 5 8 3 4Sample Output16思路树形dp入门题开始考虑只要对于每一个节点要么选择最左端要么选择最右端点显然这一策略是正确的。然后假设根节点权值确定整棵树的状态即确定然后按照dfs序正向状态转移两种状态取较大者作为最优解。这种贪心策略是不对的如父节点到子节点的左右边界差值一致这时候该怎么选择。但如果逆向考虑就不会有类似问题了这一点倒是考虑到了这写出了代码但状态转移条件搞错了具体说错误原因转移时只考虑了父节点和子节点间差值的大小而没有加上子节点所在子树的整个权值所以导致选择出的并不是全局最优解。代码实现#include stdio.h #include string.h #include iostream #include algorithm #define inf 0x3f3f3f3f using namespace std; const int N 1e5100; const int M 2e5100; int head[N],ver[M],Next[M],tot; void add(int x,int y) { ver[tot]y; Next[tot]head[x]; head[x]tot; } long long dp[N][2]; int Left[N],Right[N]; void dfs(int x,int pre) { long long a,b,c,d; for(int ihead[x]; i; iNext[i]) { int yver[i]; if(i(pre^1))continue; dfs(y,i); aabs(Left[y]-Left[x]); babs(Right[y]-Left[x]); cabs(Left[y]-Right[x]); dabs(Right[y]-Right[x]); //转移条件易错 if(dp[y][0]adp[y][1]b) dp[x][0]dp[y][0]a; else dp[x][0]dp[y][1]b; if(dp[y][0]cdp[y][1]d) dp[x][1]dp[y][0]c; else dp[x][1]dp[y][1]d; } } int main() { #ifdef MYHOME_Wjvje freopen(input.txt,r,stdin); #endif int t,n; scanf(%d,t); long long ans; while(t--) { tot1; ans0; scanf(%d,n); memset(head,0,sizeof(head)); memset(Next,0,sizeof(Next)); memset(dp,0,sizeof(dp)); for(int i1; in; i) { int x,y; scanf(%d%d,x,y); add(x,y); add(y,x); } for(int i1; in; i) scanf(%d%d,Left[i],Right[i]); dfs(1,0); ansmax(dp[1][0],dp[1][1]); printf(%lld\n,ans); } return 0; }THE END;

百度之星 Diversity （简单树形dp）

相关推荐

长期投资与复利效应：财富积累的核心策略

企业私域流量团队搭建与高效运营指南

Windows 11 添加网络打印机总是连接失败：从设备发现到 TCP/IP 端口的排查记录

更多资讯

Voyager 資料夾管理指南：為 Gemini 與 AI Studio 的 AI 對話打造真正的「檔案系統」

gatsby-source-graphql 插件全解析：将任意第三方 GraphQL API 缝合进 Gatsby 数据层

Lightweight Charts v3 到 v4 迁移指南：破坏性变更逐项分析与实战改造方案

FoundationDB 存储基准测试上 RAM Disk：mako_storage_bench.sh 在 okteto 开发 Pod 上的 tmpfs 实践指南

Trigger.dev SDK 公共包修改规范：Changesets 发布流程、版本策略与 @trigger.dev/core 子路径导入指南

swagger-codegen 生成的 Android Volley 客户端中 Pet 模型完整解析

今日更新

OneUptime 自定义探针（Custom Probe）部署实战：私网监控、代理配置与断连排障全指南

大众TL52625前端框架材料要求详解：从性能测试到落地执行

TiXL 浮点运算算子库 Lib.numbers.float 完全指南：44 个算子的参数详解、源码原理与实战串联

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？