算法课程笔记——路径相关树形DP

算法课程笔记——路径相关树形DP

#include<bits/stdc++.h>usingnamespacestd;
usingLL = longlong;
constintN = 2005;
vector<int>e[N],t;
structasdf{vector<int> vec;
    LL val;
};
vector<asdf>w[N];
LL dp[N];
intn,m,k,dep[N]={1},f[N];
voiddfs(intu){
    for(autov:e[u])
    {
        dfs(v);
        dp[u]+=dp[v];
    }
    for(autot:w[u])
    {
        LL sum=dp[u];
        for(autonw:t.vec)
        {
            sum-=dp[nw];
            for(autov:e[nw]) sum+=dp[v];
        }
        dp[u]=max(dp[u],sum+t.val);
    }
}
intmain(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(inti=2;i<=n;++i)
    {
        cin>>f[i];
        e[f[i]].push_back(i);
        dep[i]=dep[f[i]]+1;
    }
    for(inti=1,x,y;i<=m;++i)
    {
        LL val;
        cin>>x>>y>>val;
        t.clear();
        while(x!=y)
            if(dep[x]>dep[y]) t.push_back(x),x=f[x];
            elset.push_back(y),y=f[y];
        t.push_back(x);
        w[x].push_back({t,val});
    }
    dfs(1);
    cout<<dp[1];
    return0;
}

#include<bits/stdc++.h>usingnamespacestd;
usingLL=longlong;
intn,m;
constintN=2005;
structasdf{intx;
    LL val;
};
vector<asdf> w[N];
vector<int>e[N];
intdep[N];
LL dp[N][N];
voiddfs(intu){
    LL sum=0;
    for(inti=1;i<=dep[u];++i) dp[u][i]=1e18;
    for(autov:e[u])
    {
        dfs(v);
        sum+=dp[v][dep[u]+1];
        if(sum>=1e18)
        {
            cout<<-1;
            exit(0);
        }
        for(inti=1;i<=dep[u];++i)
            dp[u][i]=min(dp[u][i],dp[v][i]-dp[v][dep[u]+1]);
    }
    for(inti=1;i<=dep[u];++i) dp[u][i]+=sum;
    for(autov:w[u])
        dp[u][dep[v.x]]=min(dp[u][dep[v.x]],sum+v.val);
    for(inti=2;i<=dep[u];++i) dp[u][i]=min(dp[u][i],dp[u][i-1]);
}
intmain(){
    cin>>n>>m;
    dep[1]=1;
    for(inti=2;i<=n;++i)
    {
        intf;
        cin>>f;
        e[f].push_back(i);
        dep[i]=dep[f]+1;
    }
    for(inti=1;i<=m;++i)
    {
        intx,y;
        LL val;
        cin>>x>>y>>val;
        if(dep[x]>dep[y]) swap(x,y);
        w[y].push_back({x,val});
    }
    dfs(1);
    cout<<dp[1][1];
    return0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/624043.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【ubuntu20.04运行python文件时,报错No module named ‘rospkg’】

**问题原因&#xff1a;**一般来说&#xff0c;并不是真的缺少rospkg&#xff0c;而是系统中存在多个python版本导致的混乱 检查python版本 Ubuntu20.04 —— pyhon3.8 sudo apt-get install python3.8最新版本&#xff0c;如下图所示 查看python3.8的位置 whereis python…

【Redis】Redis 主从集群(一)

为了避免 Redis 的单点故障问题&#xff0c;可以搭建一个 Redis 集群&#xff0c;将数据备份到集群中的其它节点上。若一个 Redis 节点宕机&#xff0c;则由集群中的其它节点顶上 1.主从集群搭建 Redis 的主从集群是一个“一主多从”的读写分离集群。集群中的 Master 节点负责…

OBS插件--源录制

源录制 将应用这个滤镜的源录制成视频保存下来&#xff0c;可以选择音轨&#xff0c;也可以针对应用此滤镜的源单独的推流等。 如果在直播或录制视频的过程中场景里面布置了多个源&#xff0c;而只想保存其中一个源的视频或音频这个插件非常使用。 下面截图演示下操作步骤&a…

03-数据结构(一)

链接&#xff1a;C# 数据结构_哔哩哔哩_bilibili https://www.bilibili.com/video/BV1a541147Nk/?spm_id_from333.337.search-card.all.click&vd_source6eb7d966aa03ff5cb02b63725f651e68 链接&#xff1a;使用 C#.Net 学习掌握数据结构 (更新中)_哔哩哔哩_bilibili 一…

企业安全必备利器:专业级加密软件介绍

随着信息技术的迅猛发展&#xff0c;数据安全问题日益凸显&#xff0c;专业级加密软件应运而生&#xff0c;成为保护数据安全的重要工具。本文将对专业级加密软件进行概述&#xff0c;分析其特点、应用场景及分享。 一、专业级加密软件概述 专业级加密软件是指那些采用高级加密…

Spring Boot集成Druid快速入门Demo

1.什么是Druid&#xff1f; Druid连接池是阿里巴巴开源的数据库连接池项目。Druid连接池为监控而生&#xff0c;内置强大的监控功能&#xff0c;监控特性不影响性能。功能强大&#xff0c;能防SQL注入&#xff0c;内置Loging能诊断Hack应用行为。 2.mysql环境搭建 第一个mysql数…

Java线程池:当核心线程数为 0 时,任务来了的执行流程

先说结论&#xff1a;创建一个临时线程直接执行 ThreadPoolExecutor.excute() public void execute(Runnable command) {if (command null)throw new NullPointerException();int c ctl.get();if (workerCountOf(c) < corePoolSize) {if (addWorker(command, true)) retu…

石墨烯材料商汉烯科技授权世强硬创,代理产品具备高导热/导电特点

近日&#xff0c;武汉汉烯科技有限公司&#xff08;下称“汉烯科技”&#xff0c;英文&#xff1a;HANXI TECH&#xff09;与世强先进&#xff08;深圳&#xff09;科技股份有限公司&#xff08;下称“世强先进”&#xff09;达成授权代理合作&#xff0c;面向锂电新能源、电子…

Node.js初步学习

1.什么是Node.js Node.js是一个跨平台Javascript运行环境&#xff0c;使开发者可以搭建服务器端的Javascript应用程序。 编写后端程序&#xff0c;提供网页资源浏览功能等等&#xff1b; 前端工程化&#xff1a;为后续学习vue和react等框架做铺垫&#xff1b;前端工程化是指…

海思Hi3065H 200MHz 高性能 RISCV32 A² MCU

这是一款海思自研的RISCV32内核的高性能实时控制专用MCU&#xff0c; 具有高性能、高集成度、高可靠性、易开发的特点&#xff0c;同时还有嵌入式AI能力。 CPU • RISC-V200MHzFPU 存储 • Up to 152KB Code Flash • 8KB Data Flash • 16KB SRAM 个人认为这是MCU梯队非常…

精英都是时间控,职场精英的完美一天!

如何超高效使用24小时 每个人的一天都只有24小时&#xff0c;使用时间的方法将决定整个人生。时间管理术并不提倡把自己忙死榨干&#xff0c;而是通过在合适的时间做合适的事情&#xff0c;把大脑机能发挥到极致&#xff0c;从而提高效率&#xff0c;节省下更多时间用于生活与…

iOS xib知识总结

一、bug总结 1.could not insert new outlet connection 解决办法&#xff1a;操作步骤就是选中出问题的.m和.h文件&#xff0c;点删除键&#xff0c;然后选“Remove Reference”&#xff0c;这样就不会真正删除文件。接着选“File -> Add Files to …”菜单&#xff0c;在…

macOS上使用qt creator编译调试ffmpeg.c

1 前言 上文macOS上将ffmpeg.c编译成Framework介绍了使用xocde将ffmpeg.c编译成Framework的方法&#xff0c;这里列举另外一种办法&#xff0c;就是用qt creator来完成这件事情。 编译环境如下&#xff1a; qt creator 9.0.2&#xff1b;ffmpeg release/6.1; 2 编译ffmpeg.c 大…

算法加密-简介

前言 在遥远的古代&#xff0c;信息的传递至关重要。战争时期&#xff0c;将领们需要确保自己的作战计划不被敌人知晓。 有一次&#xff0c;一位聪明的将军想要给远方的盟友传递一份机密战略部署。他想到了一个办法&#xff0c;用一种特殊的符号来替代文字。他和盟友事先约定好…

CST电磁仿真结果比较与查看参数扫描的结果【入门教学】

Results 仿真结果的比较 使用New Tree Folder&#xff01; Navigation Tree > 1D Results > New Tree Folder 在使用CST软件时&#xff0c;希望比较两个仿真数据时&#xff0c;可以使用New Tree Folder。点击导航树中的1D Results文件夹然后右键选择New Tree Folder就…

【C++】再识构造函数:初始化列表新方式

欢迎来到CILMY23的博客 &#x1f3c6;本篇主题为&#xff1a; 再识构造函数&#xff1a;初始化列表新方式 &#x1f3c6;个人主页&#xff1a;CILMY23-CSDN博客 &#x1f3c6;系列专栏&#xff1a;Python | C | C语言 | 数据结构与算法 | 贪心算法 | Linux &#x1f3c6;感…

k8s endpoint

Endpoint Service 并不是和 pod 直接相连的&#xff0c;Endpoint 介于两者之间。Endpoint 资源就是暴露一个服务的 IP 地址和端口的列表。 虽然在 spec 服务中定义了 pod 选择器&#xff0c;但在重定向传入连接时不会直接使用它。选择器用于构建 IP 和端口列表&#xff0c;然…

Pikachu 靶场 SQL 注入通关解析

前言 Pikachu靶场是一种常见的网络安全训练平台&#xff0c;用于模拟真实世界中的网络攻击和防御场景。它提供了一系列的实验室环境&#xff0c;供安全专业人士、学生和爱好者练习和测试他们的技能。 Pikachu靶场的目的是帮助用户了解和掌握网络攻击的原理和技术&#xff0c;…

网络基础_01

1.网络通信过程 1.1架构 c/s架构 c:client 服务器 s:server 客户端 客户端&#xff1a;安装在你电脑上的qq&#xff0c;浏览器(360浏览器、chrome浏览器、IE浏览器等)&#xff0c;当我们使用qq发送消息的时候&#xff0c;消息先发送到了腾讯&#xff0c;然后腾讯在转发到你朋友…

目标检测实战(八): 使用YOLOv7完成对图像的目标检测任务(从数据准备到训练测试部署的完整流程)

文章目录 一、目标检测介绍二、YOLOv7介绍三、源码/论文获取四、环境搭建4.1 环境检测 五、数据集准备六、 模型训练七、模型验证八、模型测试九、错误总结9.1 错误1-numpy jas mp attribute int9.2 错误2-测试代码未能跑出检测框9.3 错误3- Command git tag returned non-zero…