流(树形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;
}


目录
相关文章
|
4月前
|
消息中间件 Kubernetes JavaScript
动态规划-区间、计数类DP问题总结
动态规划-区间、计数类DP问题总结
|
7月前
|
算法
求最大连续子段和 的 dp算法
对于这样的问题,我们可以直接用暴力,一个双重循环,虽说可以,但也没有更高明的方法? 我们再分析这个问题,如果我们知道了某个数前面一段数的和,我们就该考虑把这个数加入到前一段,还是重新开始一段。这个地方很重要,如果前一段的和小于0,我们重新建一段,反之加到前一段。这样我们就可以把n个数分成几段了,且每一段都求出了他们的和,然后再循环一次求出最大的一个和,我们就得到想要的结果了,也可以在分段的时候直接求结果。
27 0
|
11天前
树形dp常见类型——换根dp
树形dp常见类型——换根dp
动态规划(DP)——区间DP
动态规划(DP)——区间DP
|
9月前
|
人工智能
动态规划(DP)——线性DP
动态规划(DP)——线性DP
|
11月前
|
存储 算法
dp 就 dp ,数位dp是什么意思 ?
dp 就 dp ,数位dp是什么意思 ?
227 0
|
人工智能
(闫氏dp分析法)(线性dp)(区间类dp)AcWing 895. 最长上升子序列
(闫氏dp分析法)(线性dp)(区间类dp)AcWing 895. 最长上升子序列
66 0
|
机器学习/深度学习 定位技术
【每日一题Day109】LC1210穿过迷宫的最少移动次数 | BFS+dp
思路:使用BFS搜索,队列中存放三元组[蛇尾的横轴坐标x,蛇尾的纵轴坐标y,蛇的状态],当蛇为水平时,状态为0;当蛇为竖直时,状态为1
94 1
【每日一题Day109】LC1210穿过迷宫的最少移动次数 | BFS+dp
AcWing288. 休息时间(环形DP)
AcWing288. 休息时间(环形DP)
83 0