距离和(换根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;
ll qpow(int a, int b) {
  ll ans = 1;
  while (b) {
    if (b & 1) ans = ans * a;
    a = (ll)a * a;
    b >>= 1;
  }
  return ans;
}
inline int read()
{
  int X = 0;
  bool flag = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flag = 0;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    X = (X << 1) + (X << 3) + ch - '0';
    ch = getchar();
  }
  if (flag) return X;
  return ~(X - 1);
}
inline void write(int X)
{
  if (X < 0) {
    X = ~(X - 1);
    putchar('-');
  }
  if (X > 9) write(X / 10);
  putchar(X % 10 + '0');
}
struct dsu {
  private:
    vector<int> par, ran, cnt;
  public:
    dsu(int n) {
      par.resize(n, 0);
      iota(par.begin(), par.end(), 0);
      ran.resize(n, 0);
      cnt.resize(n, 1);
    }
    int find(int x) {
      if (par[x] == x)return x;
      else return par[x] = find(par[x]);
    }
    bool unite(int x, int y) {
      x = find(x), y = find(y);
      if (x == y) return false;
      if (ran[x] < ran[y]) {
        par[x] = y;
        cnt[y] += cnt[x];
      }
      else {
        par[y] = x;
        cnt[x] += cnt[y];
        if (ran[x] == ran[y])ran[x]++;
      }
      return true;
    }
    bool same(int x, int y) {
      return find(x) == find(y);
    }
    int getcnt(int x) {
      return cnt[find(x)];
    }
};
int n;
vector<int>g[N];
int sz[N];
int d[N];
int dfs1(int u, int f)
{
  sz[u] = 1;
  for (auto x : g[u])
  {
    if (x == f) continue;
    sz[u] += dfs1(x, u);
    d[u] += d[x] + sz[x];
  }
  return sz[u];
}
void dfs(int u, int f)
{
  for (auto x : g[u])
  {
    if (f == x) continue;
    d[x] = d[u] - 2 * sz[x] + n;
    dfs(x, u);
  }
}
void solve()
{
  cin >> n;
  for (int i = 1; i < n; i++)
  {
    int x, y;
    cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs1(1, -1); // 求1到每个带点的距离
  //cout << d[1] << endl;
  dfs(1, -1);
  for (int i = 1; i <= n; i++)
  {
    cout << d[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;
}


目录
相关文章
|
存储 JavaScript 中间件
Nuxt.js:用 Vue.js 打造服务端渲染应用程序(二)
Nuxt.js:用 Vue.js 打造服务端渲染应用程序
|
Java 关系型数据库 测试技术
基于SpringBoot的特色农产品销售设计与实现
基于SpringBoot的特色农产品销售设计与实现
7041 1
基于SpringBoot的特色农产品销售设计与实现
|
设计模式 运维 安全
被困住的职场人|这三年帮助我走出困境的书籍分享
本文讲述作者从不习惯读书到领悟读书益处后各个阶段的职场感悟,对各类书籍做了详细的总结分享,希望对大家有所裨益。
10948 4
|
机器学习/深度学习 人工智能 自然语言处理
什么是人工智能大模型?
@[TOC](目录) ![在这里插入图片描述](https://img-blog.csdnimg.cn/898355808b574ee4a0d7f64b4e8fe581.png) 人工智能大模型是指具有巨大参数量和复杂结构的人工智能模型。它们通过深度学习和神经网络技术,能够处理大规模的数据集和复杂的任务。这些大模型在自然语言处理、计算机视觉、语音识别等领域展现了强大的性能和能力。 以下是对人工智能大模型的详细介绍: # 1. 人工智能大模型的概述: - 人工智能模型的分类:人工智能模型可以分为浅层模型和深度学习模型两大类。大模型属于深度学习模型,具有多层结构和大量的参数。
2080 0
|
Linux Windows
Windows文件直接上传到Linux
Windows文件直接上传到Linux
313 0
|
机器学习/深度学习 存储 传感器
带你读《创新之巅: 未来十年重构商业的六大战略性技术》第三章自动化机器—机器人、合作机器人、无人机和自动驾驶汽车3.2机器人可以做什么(一)
《创新之巅: 未来十年重构商业的六大战略性技术》第三章自动化机器—机器人、合作机器人、无人机和自动驾驶汽车3.2机器人可以做什么
|
前端开发 测试技术 iOS开发
|
分布式计算 Hadoop
Hadoop2.7实战v1.0之动态添加、删除DataNode节点及复制策略导向
一.环境   IP Host 及安装软件 部署模块 ...
1331 0