尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
百度之星 Diversity (简单树形dp)
题意描述Diversity给你一棵n个点的树对于节点ii你要给它标上一个[l​i​​,r​i​​]之间的数要求所有边两端节点上标的数字的差的绝对值的总和最大。Input第一行一个整数T T(1≤T≤5)表示数据组数。对于每组数据格式如下。第一行一个正整数n(2≤n≤10​5​​)。接下来n-1行每行两个正整数 u, v(1≤u,v≤n)表示一条边。接下来nn行第ii行两个正整数l​i​​,r​i​​(1 ≤ l​i ​​≤ r​i ​​≤ 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;
RELATED

相关推荐

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

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

1. 为什么耐心是赚钱的第一门槛 这个标题虽然带着强烈的情绪色彩,但确实戳中了一个关键问题:在追求财富的道路上,大多数人不是缺乏机会,而是缺乏持续投入的耐心和毅力。我见过太多人热衷于寻找"快速致富"的捷径&#xf…

📅 2026/11/13 14:57:19
企业私域流量团队搭建与高效运营指南

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

1. 私域运营团队搭建的核心逻辑 私域流量运营已经成为企业数字化营销的标配能力,但90%的企业在团队搭建阶段就埋下了失败的种子。我在操盘多个行业头部品牌的私域项目时发现,团队架构与业务规模的匹配度直接决定了私域ROI的高低。一个200人团队的配置方案…

📅 2026/9/21 10:03:04
Windows 11 添加网络打印机总是连接失败:从设备发现到 TCP/IP 端口的排查记录

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

Windows 11 添加网络打印机时,搜索列表里看不到设备、能看到却连接失败,或者安装完成后任务一直停在队列中,问题不一定是驱动包下载错了。网络打印涉及设备地址、发现方式、端口指向、型号匹配和后台服务多个环节。下面按从网络可达性到实际输…

📅 2026/9/21 10:26:53
MORE NEWS

更多资讯

📰

社会人电工证报考官方回应:怕考不过白交培训费?看许昌劳务班组怎么避坑

社会人电工证报考官方回应:怕考不过白交培训费?看许昌劳务班组怎么避坑 怕考不过白交培训费?这是不少准备报考社会人电工证的打工人心头最大的坎儿。我认识的几个电工师傅,就是因为听信了培训机构“包过”的话,结果考试挂了,钱白花了,还得重新报名,耽…

📰

大学消防电工证怎么考 在哪考别被中介坑了

大学消防电工证怎么考 在哪考别被中介坑了 你是不是正愁着不知道 大学消防电工证怎么考 ,在网上搜来搜去,一堆中介电话和真假难辨的信息,搞得你不敢轻易报名?其实,考这个证不难,关键是 在哪考…

📰

低压电工证建议报考吗?含金量高到你想不到

低压电工证建议报考吗?含金量高到你想不到 怕考不过白交培训费?别急,低压电工证这事儿,真不是你想的那么简单。特别是像咱这种在周口干水利工程的,天天跟电打交道,证没考下来,项目干不了,工资也别想拿全。这证,不光是资格,更是安全和责任的象征。而…

📰

刚考电工证算什么级别值不值得考

刚考电工证算什么级别值不值得考 学历不高怕报不上名?别担心,电工证这玩意儿,其实你只要符合基本条件就能报,而且在很多行业里,它真不是“花架子”。今天咱们就从【刚考电工证算什么级别】这个点出发,聊聊你最关心的几个问题:电工证到底值不值得考?它…

📰

罗源电工证培训机构多少钱?工地太忙根本没时间复习考试

罗源电工证培训机构多少钱?工地太忙根本没时间复习考试 工地太忙根本没时间复习考试,你是不是也经常在工地上加班加点,连吃饭的时间都紧张,更别说抽空复习电工证考试了?别急,罗源电工证培训机构已经帮你想到这一点了, 多少钱…

📰

外检员考电工证保姆级教程:实操考试心里没底怕挂科?手把手教你顺利取证

外检员考电工证保姆级教程:实操考试心里没底怕挂科?手把手教你顺利取证 实操考试心里没底怕挂科?你不是一个人。很多外检员在准备电工证考试时,最大的担忧就是实操部分,担心操作不熟练、流程不熟悉,最后考不过白费时间和金钱。这篇文章就是为你量身定制…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬