比赛 集训 评测结果 TTTTTTTTTT
题目名称 一无所有 最终得分 0
用户昵称 LikableP 运行时间 59.991 s
代码语言 C++ 内存使用 7.36 MiB
提交时间 2025-07-03 12:07:30
显示代码纯文本
#include <algorithm>
#include <cstdio>

template <typename T> T read();
template <typename T> void write(T, char);
void AddEdge(int, int);
void dfs(int, int);
int LCA(int, int);

const int MAXN = 1e5 + 10;

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

int n;
int deg[MAXN];
int leaves[MAXN], lcnt;
int depth[MAXN], grd[MAXN][18];
int ans;

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>();
    deg[u]++, deg[v]++;
    AddEdge(u, v);
    AddEdge(v, u);
  }

  dfs(1, 0);

  for (int i = 1; i <= n; ++i) {
    if (deg[i] == 1) leaves[++lcnt] = i;
  }

  for (int t = 1; t <= n; ++t) {
    dfs(t, 0);
    ans = lcnt;
    for (int i = 1; i <= lcnt; ++i) {
      for (int j = i + 1; j <= lcnt; ++j) {
        int x = leaves[i], y = leaves[j], lca = LCA(x, y);
        int mindis = ::std::min(depth[x] - depth[lca], depth[y] - depth[lca]);
        int nothingdis = ::std::abs(depth[t] - depth[lca]);
        if (nothingdis >= mindis) ans--;
      }
    }
    write(ans == 0 ? 1 : ans, '\n');
  }
  return 0;
}

int LCA(int x, int y) {
  if (depth[x] < depth[y]) ::std::swap(x, y);
  for (int i = 17; i >= 0; --i) {
    if (depth[grd[x][i]] >= depth[y]) {
      x = grd[x][i];
    }
  }
  if (x == y) return x;
  for (int i = 17; i >= 0; --i) {
    if (grd[x][i] != grd[y][i]) {
      x = grd[x][i];
      y = grd[y][i];
    }
  }
  return grd[x][0];
}

int head[MAXN], edgeNum;
void dfs(int now, int fa) {
  depth[now] = depth[fa] + 1;
  grd[now][0] = fa;
  for (int i = 1; i <= 17; ++i) {
    grd[now][i] = grd[grd[now][i - 1]][i - 1];
  }
  for (int i = head[now]; i; i = edge[i].next) {
    int v = edge[i].v;
    if (v == fa) continue;
    dfs(v, now);
  }
}

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

#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);
}