流(树形dp,换根dp)

简介: 流(树形dp,换根dp)

前置知识看这里

注意父亲节点为叶子节点的情况就行了

/*********************************************************************
    程序名:
    版权: Joecai
    作者: Joecai
    日期: 2022-04-13 23:47
    说明:
*********************************************************************/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
# define rep(i,be,en) for(int i=be;i<=en;i++)
# define pre(i,be,en) for(int i=be;i>=en;i--)
#define ll long long
#define endl "\n"
#define LOCAL
#define pb push_back
#define int long long
typedef pair<ll, ll> PII;
#define eb emplace_back
#define sp(i) setprecision(i)
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
struct node
{
  ll to;
  ll w;
};
vector<node>g[N];
ll du[N];
ll sum[N];
void dfs1(int u, int f)
{
  for (auto x : g[u])
  {
    if (x.to == f) continue;
    dfs1(x.to, u);
    if (du[x.to] > 1)
    {
      sum[u] += min(x.w, sum[x.to]);
    } else
    {
      sum[u] += x.w;
    }
  }
}
void dfs(int u, int f)
{
  for (auto x : g[u])
  {
    if (x.to == f) continue;
    if (du[x.to] > 1)
    {
      sum[x.to] = sum[x.to] + min((sum[u] - min(x.w, sum[x.to])) == 0 ? x.w : (sum[u] - min(x.w, sum[x.to])), x.w);
    } else
      sum[x.to] = min(sum[u] - x.w, x.w);
    dfs(x.to, u);
  }
  return;
}
void solve()
{
  int n;
  cin >> n;
  for (int i = 1; i <= n - 1; i++)
  {
    int x, y, w;
    cin >> x >> y >> w;
    du[x]++;
    du[y]++;
    g[x].push_back({y, w});
    g[y].push_back({x, w});
  }
  dfs1(1, 0);
  dfs(1, 0);
  for (int i = 1; i <= n; i++)
  {
    cout << sum[i] << endl;
  }
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  //#ifdef LOCAL
  //freopen("data.in.txt","r",stdin);
  //freopen("data.out.txt","w",stdout);
  //#endif
  int __ = 1;
  //cin>>__;
  while (__--)
  {
    solve();
  }
  return 0;
}


目录
相关文章
|
2月前
|
机器学习/深度学习 人工智能 Java
优先队列 priority_queue详解
说到,priority_queue优先队列。必须先要了解啥是堆与运算符重载(我在下方有解释)。否则只知皮毛,极易忘记==寸步难行。但在开头,还是简单的说下怎么应用。
666 1
|
存储 Serverless C++
【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]
【C++入门到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入门 ]
537 1
|
IDE Linux 开发工具
IntelliJ IDEA2022破解IDEA2022.2永久破解激活教程
IDEA 目前已经更新到最新的 2022.2.2 版本了,群里的小伙伴私聊问我,为啥之前 2021.3.1 的激活套路对新版本 2022.2.2 不管用了,是个什么情况? 很显然,IDEA 官方发现了这种破解路数,新版本加入了更严厉的反制破解。所以说,小伙伴们破解成功了以后,尽量不要升级 IDEA, 不然大概率又不行了。 好在z大又更新了新的补丁,针对最新版本,这边笔者亲测可行,仅以下文记录本人 IntelliJ IDEA 2022.2.2 版本的激活破解到 2099 年的全过程,步骤非常详细,跟着图文来就行~
70053 3
IntelliJ IDEA2022破解IDEA2022.2永久破解激活教程
|
人工智能
【蓝桥】蓝桥小白入门赛8
A、签到 B、结论性排序 C、找规律+暴力 D、找规律+递推+贪心 E、找规律+贪心 F、dp
205 11
|
C语言
【C深度解剖】取模与取余
【C深度解剖】取模与取余
541 0
|
机器学习/深度学习 算法 Java
从斐波那契数列到递归
大家好,我是王有志。今天我们要通过经典数学问【题斐波那契数列】来学习非常重要的编程技巧:递归。
664 1
从斐波那契数列到递归
|
人工智能 算法
什么是算法?
当人们提到“算法”一词,往往就会把它们当成专属于“人工智能”的范畴,很多专业的计算机人士也是,提起算法就头疼,不知道如何学习算法,慢慢的对算法就会失去兴趣,算法不仅仅是计算机行业特有的,在我们的生活中也处处存在着算法,算法是专注于解决问题的过程和方法。
448 1
什么是算法?
|
11天前
|
人工智能 JSON 供应链
畅用7个月无影 JVS Claw |手把手教你把JVS改造成「科研与产业地理情报可视化大师」
LucianaiB分享零成本畅用JVS Claw教程(学生认证享7个月使用权),并开源GeoMind项目——将JVS改造为科研与产业地理情报可视化AI助手,支持飞书文档解析、地理编码与腾讯地图可视化,助力产业关系图谱构建。
23465 10
畅用7个月无影 JVS Claw |手把手教你把JVS改造成「科研与产业地理情报可视化大师」