当前位置: 首页 > 编程日记 > 正文

HDU5886 Tower Defence 【两遍树形dp】【最长链预处理】

题意:N个点的一棵带权树。切掉某条边的价值为切后两树直径中的最大值。求各个边切掉后的价值和(共N-1项)。

解法一:

强行两遍dp,思路繁琐,维护东西较多:

dis表示以i为根的子树的直径,dis2表示切掉以i为根的子树后的直径。

第一遍dp,记录

down[][0]:从i结点向下的最大距离
  down[][1]:与down[][0]无交集的向下次大距离
  dis:以i为根的子树的直径

第二遍dp,记录

up:从i结点向上的最远距离, 可以是w+父节点的up,也可以是w+父节点的down(判断一下down是否与w有重合)
  dis2:切掉以i为根的子树后的直径

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 #define X first
  4 #define Y second
  5 #define pii pair<int, int>
  6 #define mp make_pair
  7 typedef long long ll;
  8 const int N = 1e5+5;
  9 void gmax(int& a, int b){ if(a < b) a = b;}
 10 int n;
 11 ll ans;
 12 int down[N][2], up[N], dis[N], dis2[N];
 13 
 14 int head[N], nex[N*2], tot;
 15 pii edge[N*2];
 16 void init(){
 17     tot = 0;
 18     memset(head, -1, sizeof(head));
 19     memset(down, 0, sizeof(down));
 20     memset(up, 0, sizeof(up));
 21     memset(dis, 0, sizeof(dis));
 22     memset(dis2, 0, sizeof(dis2));
 23 }
 24 void add(int u, int v, int w){
 25     edge[tot] = mp(v, w);
 26     nex[tot] = head[u];
 27     head[u] = tot++;
 28 }
 29 //down[][0]:从i结点向下的最大距离
 30 //down[][1]:与down[][0]无交集的向下次大距离
 31 //dis:以i为根的子树的直径
 32 void dfs(int fa, int x){
 33 //    printf("dfs x %d, fa %d\n", x, fa);
 34 //down[x][0] = down[x][1] = dis[x] = dis2[x] = up[x] = 0;
 35     for(int i = head[x]; ~i; i = nex[i]){
 36         int y = edge[i].X, w = edge[i].Y;
 37         if(y == fa) continue ;
 38         dfs(x, y);
 39         if(down[y][0]+w > down[x][0])
 40             down[x][1] = down[x][0], down[x][0] = down[y][0]+w;
 41         else if(down[y][0]+w > down[x][1])
 42             down[x][1] = down[y][0]+w;
 43         gmax(dis[x], dis[y]);
 44     }
 45     gmax(dis[x], down[x][0]+down[x][1]);
 46 }
 47 //up:从i结点向上的最远距离
 48 //dis2:切掉以i为根的子树后的直径
 49 multiset<int>::iterator it;
 50 void dfs2(int fa, int x){
 51     if(fa != -1) ans += max(dis[x], dis2[x]);
 52 //    printf("fa %d, x %d\n", fa, x);
 53     multiset<int> se, se2;//兄弟树的直径, x往各个兄弟树的最长路
 54     for(int i = head[x]; ~i; i = nex[i]){
 55         int y = edge[i].X, w = edge[i].Y;
 56         if(y == fa) continue ;
 57         se.insert( dis[y] );
 58         se2.insert( down[y][0]+w );
 59     }
 60     for(int i = head[x]; ~i; i = nex[i]){
 61         int y = edge[i].X, w = edge[i].Y;
 62         if(y == fa) continue ;
 63         up[y] = up[x]+w;
 64         if(down[y][0]+w == down[x][0])
 65             gmax(up[y], down[x][1]+w);
 66         else gmax(up[y], down[x][0]+w);
 67         it = se.find( dis[y] ), se.erase(it);
 68         it = se2.find( down[y][0]+w ), se2.erase(it);
 69         dis2[y] = dis2[x];
 70         if(!se.empty())
 71             gmax(dis2[y], *se.rbegin());
 72         if(se2.empty()) gmax(dis2[y], up[x]);
 73         else gmax(dis2[y], up[x]+*se2.rbegin());
 74         if(se2.size() >= 2){
 75             int tmp = 0;
 76             it = se2.end();
 77             tmp += *--it;
 78             tmp += *--it;
 79             gmax(dis2[y], tmp);
 80         }
 81         dfs2(x, y);
 82         se.insert( dis[y] );
 83         se2.insert( down[y][0]+w );
 84     }
 85 }
 86 void debug(int n){
 87     for(int i = 1; i <= n; i++)
 88         printf("%d: down0 %d, down1 %d, dis %d, dis2 %d, up %d\n", i, down[i][0], down[i][1], dis[i], dis2[i], up[i]);
 89 }
 90 int main(){
 91     int t, u, v, w; scanf("%d", &t);
 92     while(t--) {
 93         init();
 94         scanf("%d", &n);
 95         for(int i = 1; i < n; i++){
 96             scanf("%d%d%d", &u, &v, &w);
 97             add(u, v, w), add(v, u, w);
 98         }
 99         ans = 0;
100         dfs(-1, 1);
101         dfs2(-1, 1);
102         printf("%lld\n", ans);
103     }
104     return 0;
105 }
View Code

解法二:

先求出原树的直径。

从直径两端分别来一次dp

切的边不在直径上,价值为直径;

切的边在直径上,由直径两端的dp得解。

转载于:https://www.cnblogs.com/dirge/p/5975794.html

相关文章:

NPOI读取Excel数据应用

NPOI 是 POI 项目的 .NET 版本。使用 NPOI 你就可以在没有安装 Office 或者相应环境的机器上对 WORD/EXCEL 文档进行读写。NPOI是构建在POI 3.x版本之上的&#xff0c;它可以在没有安装Office的情况下对Word/Excel文档进行读写操作。 需求&#xff1a;根据excel表格提供的SVN相…

pod setup慢的解决方法

最近使用pod setup更新CocoaPods本地检索库&#xff0c;无奈只有10几k&#xff0c;还中途报错。最终通过以下步骤&#xff0c;完成更新。 1.手动下载Specs检索库 执行pod setup后&#xff0c;实质是从github上clone检索库&#xff08;https://github.com/CocoaPods/Specs&…

如何高效地爬取链家的房源信息(二)

“Python实现的链家网站的爬虫第二部分。”本系列文将以链家南京站为例&#xff0c;使用Python实现链家二手房源信息的爬虫&#xff0c;将数据爬取&#xff0c;并存入数据库中&#xff0c;以便使用。本系列第一部分&#xff1a;如何高效地爬取链家的房源信息&#xff08;一&…

C#实现HttpPost提交文件

先建立一个WebApplication Web.config <?xml version"1.0" encoding"utf-8"?><configuration><system.web><!--<globalization requestEncoding"gb2312" responseEncoding"gb2312" fileEncoding"gb231…

16年10月18号2th运算符与流程结构

---恢复内容开始--- 2th: 一&#xff1a;运算符 算数运算符 - * / %取余 9%30 自增 --自减 关系运算符 < < > > 全等于 !不等于 逻辑运算符 & | &#xff01;非 ^异或 &&短路与 || 短路或 赋值…

通用的排序按钮

排序按钮&#xff0c;使用Core Graphic绘制&#xff0c;可以指定颜色、大小、字体等&#xff1a; 使用场景如下&#xff1a; 1.使用方法 下载demo代码。将HYRankView.h和HYRankView.m代码拖入工程。 然后使用如下代码&#xff0c;即可快速添加一个名称为价格的排序按钮 HYR…

如何高效地爬取链家的房源信息(三)

“Python实现的链家网站的爬虫第三部分。”本系列文将以链家南京站为例&#xff0c;使用Python实现链家二手房源信息的爬虫&#xff0c;将数据爬取&#xff0c;并存入数据库中&#xff0c;以便使用。本系列第一部分为基础&#xff1a;如何高效地爬取链家的房源信息&#xff08;…

Swift学习总结【持续更新】

1、 try、try?、try!的区别&#xff1a; try&#xff1a;需要用catch捕捉异常&#xff0c;如&#xff1a; do {let data try encoder.encode(item) try data.write(to: dataFilePath(), options: .atomic)} catch {print("Error encoding item array:\(error.localize…

svn清理失败且乱码 问题解决(转)

由于昨天在网络不好的状态下频繁尝试svn更新&#xff0c;导致今天svn更新时出现&#xff1a;清理失败且乱码的情况如下&#xff1a; 以下是解决方案&#xff1a;1.下载sqlite3.exe ,地址为&#xff1a;http://download.csdn.net/detail/whyzzj/63465292.在D盘建立文件夹 tools …

UI学习第二篇 (控件)

UIbutton 也是一个控件&#xff0c;它属于UIControl 用的最多的就是事件响应 1. //创建按钮对象 UIButton * _botton [UIButton buttonWithType:UIButtonTypeCustom]; //设置标题 [_botton setTitle:"按住说话" forstate:UIControlStateNormal]; [_botton setTitle:…

如何高效地爬取链家的房源信息(四)

“Python实现的链家网站的爬虫第四部分&#xff0c;最后一部分。”本系列文将以链家南京站为例&#xff0c;使用Python实现链家二手房源信息的爬虫&#xff0c;将数据爬取&#xff0c;并存入数据库中&#xff0c;以便使用。本系列第一部分为基础&#xff1a;如何高效地爬取链家…

Quartz2D在项目中的实际使用

还记得大学刚学iOS那会&#xff0c;从学校图书馆借了本iOS开发的书&#xff0c;有一章节介绍了Quartz2D&#xff0c;当时看得一头雾水&#xff0c;感觉这画画线&#xff0c;画画圆有什么用呢&#x1f914;️&#xff1f;工作一段时间后&#xff0c;遇到了一些需求&#xff0c;终…

区别:电感、磁珠和零欧电阻的作用

转载&#xff1a;http://www.cntronics.com/sensor-art/80022840 【导读】电感、磁珠和零欧电阻在电路中是常见的身影。对于这三者在电路中的作用及它们之间的区别&#xff0c;相信还有很多工程师不是很清楚。不过没关系&#xff0c;小编在此为大家奉上一篇关于电感、磁珠和零欧…

【转载】Linux下安装、配置、启动Apache

原文地址:http://www.cnblogs.com/zhuque/archive/2012/11/03/2763352.html 安装Apache前准备&#xff1a; 1、检查该环境中是否已经存在httpd服务的配置文件&#xff0c;默认存储路径&#xff1a;/etc/httpd/httpd.conf&#xff08;这是centos预装的Apache的一个ent版本&#…

MIME格式解析

“ 本文介绍常见的MIME数据格式。”在协议还原中&#xff0c;不可避免地&#xff0c;经常会在各类协议内容中碰到MIME格式&#xff0c;例如标准邮件协议、HTTP协议。那么&#xff0c;什么是MIME呢&#xff1f;MIME是英文Multipurpose Internet Mail Extensions的缩写&#xff0…

AngularJs--过滤器(filter)

过滤器&#xff08;filter&#xff09;正如其名&#xff0c;作用就是接收一个输入&#xff0c;通过某个规则进行处理&#xff0c;然后返回处理后的结果。主要用在数据的格式化上&#xff0c;例如获取一个数组中的子集&#xff0c;对数组中的元素进行排序等。ng内置了一些过滤器…

【一步步学小程序】1.创建项目以及TabBar

1.创建项目 如图&#xff0c;创建项目&#xff0c;输入项目名称、选择目录&#xff0c;AppID是唯一标识&#xff0c;我们可以先点如图红框内的测试号&#xff0c;自动生成一个AppID&#xff0c;然后点新建即创建完一个新项目。 2.创建3个页面 确保如图左上角的编译器按钮是…

Yii在window下的安装方法

首先&#xff0c;在http://www.yiichina.com/上下载yii 然后&#xff0c;配置系统环境变量&#xff0c;在win8下&#xff0c;按winx&#xff0c;找到系统->高级系统设置->环境变量->path 把php的运行环境&#xff0c;加入到环境变量中&#xff0c;以分号隔开。如&…

从新手到入门,如何进入协议分析的世界

“ 协议分析与还原自学及入门指南。”有部分朋友给我发消息&#xff0c;说对协议还原很感兴趣&#xff0c;但苦于没人指导&#xff0c;希望得到我的帮助&#xff0c;问我如何进行协议分析的学习。这篇文章从初学者的角度&#xff0c;编列了一个学习指南&#xff0c;希望能对协议…

C# 学习笔记01

想写一个app可以访问数据库&#xff0c;实现对数据库的查询&#xff0c;修改等&#xff0c;突然发现知识实在有限&#xff0c;故选择C#来实现此app。 使用简单的三层架构来作为此app的架构。表现层&#xff08;UI&#xff09;、业务逻辑层&#xff08;BLL&#xff09;、数据访问…

转载 iOS js oc相互调用(JavaScriptCore) --iOS调用js

iOS js oc相互调用&#xff08;JavaScriptCore&#xff09; 从iOS7开始 苹果公布了JavaScriptCore.framework 它使得JS与OC的交互更加方便了。 下面我们就简单了解一下这个框架 首先我导入framework 方法如下 点击Linked Frameworks and Libraries 的添加后 选择 JavaScriptCor…

【一步步学小程序】2.列表展示

我们上一节已经创建了一个可以点击切换的tabbar。这节我们开始正式敲代码&#xff0c;在首页上展示一个可以上下滚动的课程列表&#xff1a; 首先打开上一节的pages/home/homeMain/homeMain.wxml文件&#xff0c;布局相关代码都会在此文件中&#xff0c;小程序的布局方式类似H…

git分支的合并

原文&#xff1a; http://gitbook.liuhui998.com/3_3.html http://gitbook.liuhui998.com/5_3.html 一、如何分支的合并在git中&#xff0c;可以使用git merge 和git rebase两个命令来进行分支的合并。git merge 和git rebase在大体上都差不多&#xff0c;下文主要以git merg…

【一步步学小程序】3. 使用自定义组件(component)

上一节创建了一个包含多个课程数据的列表。这一节我们用自定义组件&#xff08;component&#xff09;&#xff0c;来优化列表页面&#xff0c;即如图&#xff0c;我们把每个课程单元格封装为组件。 使用组件的好处&#xff1a; 自定义组件可以在不同的页面中重复使用将复杂…

《lua程序设计(第二版)》学习笔记(五)-- 函数基础

-- 第 5 章 函数-- 一种对语句和表达式进行抽象的主要机制 print(os.date()); -- 打印日期 Sun Apr 20 12:44:46 2014 -- 一看到sun&#xff0c;感慨广州没有晴天 -- 函数没有参数也要括号 -- 特殊情况:只有一个参数的时候, 并且参数一个string&#xff0f;table构造…

HTTP协议中的chunked编码解析

“ HTTP协议中的chunked传输编码全接触。”在HTTP协议中&#xff0c;服务器发往客户端的数据中&#xff0c;通常都包括HTTP头和HTTP体&#xff0c;当存在HTTP体的时候&#xff0c;HTTP体的长度通常是由HTTP头内的“Content-Length”字段确定。就像下图&#xff1a;不过&#xf…

html-css实例

<!DOCTYPE html> <html><head><meta charset"utf-8" /><title>求签</title><style type"text/css">*{margin: 0px;padding: 0px;font-family: "微软雅黑",arial,sans-serif;}body{background: url(im…

【Swift】变量/常量/类型总结

1、变量&#xff08;Variable&#xff09; 变量&#xff0c;可以理解为存放某一类型的值的容器&#xff0c;如&#xff1a; var count:Int var shouldRemind:BOOL var text:String var list:[ChecklistItem]一个变量的数据类型&#xff0c;决定了它能存放什么类型的数据。有些…

ODBC更新记录集提示”记录集为只读“

创建的ODBC应用程序默认的记录集不具有只读属性&#xff0c;但是再更新记录表时会提示”记录集为只读“&#xff0c;这是为什么呢&#xff1f; 今天看书找到了答案&#xff1a; 因为MFC中的数据库类不支持需要连接两个或者多个表的记录集更新&#xff0c;如果选择数据源的时候选…

gzip格式分析与识别

“ 介绍gzip格式&#xff0c;识别gzip压缩的数据流量。”在协议分析过程中&#xff0c;经常会发现gzip压缩的数据&#xff0c;例如在HTTP协议中&#xff0c;在HTTP头中会标示&#xff0c;内容编码为gzip、DEFLATE。但是&#xff0c;还有很多情况&#xff0c;例如一些非HTTP协议…