比赛 |
集训 |
评测结果 |
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);
}