记录编号	602400	评测结果	WWWWEEEEEE
题目名称	4165.一无所有	最终得分	0
用户昵称	LikableP	是否通过	未通过
代码语言	C++	运行时间	1.039 s
提交时间	2025-07-04 08:04:11	内存使用	2.03 MiB

#include <cstdio>
#include <cstring>

template <typename T> T read();
template <typename T> void write(T, char);
template <typename T> T min(T, T);
template <typename T> T max(T, T);
void AddEdge(int, int);
void CalcMinDisToLeavesDown(int, int);
void CalcMinDisToLeavesUp(int, int);
void Solve(int);

const int MAXN = 7e4 + 10;

struct EDGE {
  int v, next;
} edge[MAXN];

int n;
int degree[MAXN];                                 // 节点度数
int minDisToLeaves[MAXN];                         // 到最近叶节点的距离
int ans[MAXN];                                    // 答案

int main() {
  freopen("nothing.in", "r", stdin);
  freopen("nothing.out", "w", stdout);
  n = read<int>();
  for (int i = 1; i <= n - 1; ++i) {
    int u = read<int>(), v = read<int>();
    AddEdge(u, v);
    AddEdge(v, u);
    degree[u]++;
    degree[v]++;
  }

  memset(minDisToLeaves, 0x7f, sizeof minDisToLeaves);
  CalcMinDisToLeavesDown(1, 0);
  CalcMinDisToLeavesUp(1, 0);

  for (int i = 1; i <= n; ++i) {
    fprintf(stderr, "%d%c", minDisToLeaves[i], " \n"[i == n]);
  }

  Solve(1);

  for (int i = 1; i <= n; ++i) {
    write(degree[i] == 1 ? 1 : ans[i], '\n');
  }
  return 0;
}

int head[MAXN];                                   // 链式前向星表头
int siz[MAXN];                                    // 子树大小
int sum;                                          // 当前连通块的总大小
int del[MAXN];                                    // 节点 i 是否被删除
void CalcSizAndSum(int root, int fa) {
  siz[root] = 1, sum++;
  for (int i = head[root]; i; i = edge[i].next) {
    int v = edge[i].v;
    if (v == fa || del[v]) continue;
    CalcSizAndSum(v, root);
    siz[root] += siz[v];
  }
}

int centroid;                                     // 重心
void GetCentroid(int root, int fa) {
  int maxx = sum - siz[root];                     // 总节点数量-自己子树的大小=自己父亲那边的大小
  for (int i = head[root]; i; i = edge[i].next) {
    int v = edge[i].v;
    if (v == fa || del[v]) continue;
    GetCentroid(v, root);
    maxx = max(maxx, siz[v]);
  }
  if (maxx <= sum / 2) {
    centroid = root;
  }
}

#define lowbit(x) (x & -x)
int tree[MAXN << 1];
void Add(int x, int y) {
  x += n;
  for (; x <= n << 1; x += lowbit(x)) tree[x] += y;
}

int Ask(int x) {
  x += n;
  int res = 0;
  for (; x; x -= lowbit(x)) res += tree[x];
  return res;
}
#undef lowbit

void Count(int root, int fa, int len) {
  ans[root] += Ask(len);
  for (int i = head[root]; i; i = edge[i].next) {
    int v = edge[i].v;
    if (v == fa || del[v]) continue;
    Count(v, root, len + 1);
  }
}

void Update(int root, int fa, int len) {
  Add(minDisToLeaves[root] - len, 2 - degree[root]);
  for (int i = head[root]; i; i = edge[i].next) {
    int v = edge[i].v;
    if (v == fa || del[v]) continue;
    Update(v, root, len + 1);
  }
}

void Clear(int root, int fa, int len) {
  Add(minDisToLeaves[root] - len, -(2 - degree[root]));
  for (int i = head[root]; i; i = edge[i].next) {
    int v = edge[i].v;
    if (v == fa || del[v]) continue;
    Clear(v, root, len + 1);
  }
}

void Solve(int root) {
  sum = 0;
  CalcSizAndSum(root, 0);
  GetCentroid(root, 0);
  root = centroid;
  fprintf(stderr, "Now Solvig Point %d\n", root);
  del[root] = 1;
  for (int i = head[root]; i; i = edge[i].next) { // 处理跨过重心的路径
    int v = edge[i].v;
    if (del[v]) continue;
    Count(v, root, 1);
    Update(v, root, 1);
  }
  for (int i = head[root]; i; i = edge[i].next) { // 删除跨国重心的路径
    int v = edge[i].v;
    if (del[v]) continue;
    Clear(v, root, 1);
  }
  Add(minDisToLeaves[root], 2 - degree[root]);    // 处理重心刚好是端点的路径
  for (int i = head[root]; i; i = edge[i].next) {
    int v = edge[i].v;
    if (del[v]) continue;
    Count(v, root, 1);
    Update(v, root, 1);
  }
  ans[root] += Ask(0);
  Add(minDisToLeaves[root], -(2 - degree[root]));
  for (int i = head[root]; i; i = edge[i].next) { // 删除重心刚好是端点的路径
    int v = edge[i].v;
    if (del[v]) continue;
    Clear(v, root, 1);
  }
  for (int i = head[root]; i; i = edge[i].next) { // 分治
    int v = edge[i].v;
    if (del[v]) continue;
    Solve(v);
  }
}

void CalcMinDisToLeavesDown(int now, int fa) {    // 从下往上计算到最近叶节点的距离
  if (degree[now] == 1) minDisToLeaves[now] = 0;
  for (int i = head[now]; i; i = edge[i].next) {
    int v = edge[i].v;
    if (v == fa) continue;
    CalcMinDisToLeavesDown(v, now);
    minDisToLeaves[now] = min(minDisToLeaves[now], minDisToLeaves[v] + 1);
  }
}

void CalcMinDisToLeavesUp(int now, int fa) {      // 从上往下计算到最近叶节点的距离
  for (int i = head[now]; i; i = edge[i].next) {
    int v = edge[i].v;
    if (v == fa) continue;
    minDisToLeaves[v] = min(minDisToLeaves[v], minDisToLeaves[now] + 1);
    CalcMinDisToLeavesUp(v, now);
  }
}

int edgeNum;                                      // 边计数
void AddEdge(int u, int v) {
  edge[++edgeNum] = {v, head[u]};
  head[u] = edgeNum;
}

template <typename T> T max(T x, T y) {
  return x > y ? x : y;
}

template <typename T> T min(T x, T y) {
  return x < y ? x : y;
}

#define isdigit(ch) (ch >= '0' && ch <= '9')
template <typename T> T read() {
  T res = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
  return res * f;
}

template <typename T> void write(T x, char ed) {
  if (x < 0) x = -x, putchar('-');
  static int sta[sizeof(T) << 2], top = 0;
  do {
    sta[++top] = x % 10;
    x /= 10;
  } while (x);
  while (top) {
    putchar(sta[top--] ^ 48);
  }
  putchar(ed);
}