比赛 |
集训 |
评测结果 |
WWWWTTTTTT |
题目名称 |
一无所有 |
最终得分 |
0 |
用户昵称 |
OTTF |
运行时间 |
37.091 s |
代码语言 |
C++ |
内存使用 |
8.97 MiB |
提交时间 |
2025-07-03 11:40:58 |
显示代码纯文本
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
template <typename T>
void read (T& num) {
T res = 0;
T ch = getchar();
T op = 1;
while (!isdigit (ch) && ch != EOF) {
op = (ch == '-' ? -1 : 1);
ch = getchar ();
}
while (isdigit (ch)) {
res = (res * 10) + (ch - '0');
ch = getchar ();
}
num = op * res;
}
class Read {
public:
Read operator>> (auto& other) {
read (other);
return (*this);
}
};
Read in;
constexpr int N = 114514;
int n;
vector<int> graph[N];
int cc[N];
bool flag[N];
int dp[N];
int fast[N];
void doDp (int now, int dad) {
if (flag[now]) {
dp[now] = 1;
fast[now] = 0;
return;
}
dp[now] = 0;
fast[now] = N;
for (auto son : graph[now]) {
if (son != dad) {
doDp (son, now);
fast[now] = min (fast[now], fast[son] + 1);
}
}
for (auto son : graph[now]) {
if (son != dad) {
if (fast[son] <= 1) {
dp[now] += 1;
}
else {
dp[now] += dp[son];
}
}
}
}
int main () {
freopen ("nothing.in", "r", stdin);
freopen ("nothing.out", "w", stdout);
in >> n;
int u, v;
for (int i = 1; i < n; i++) {
in >> u >> v;
graph[u].emplace_back(v);
graph[v].emplace_back(u);
cc[u]++;
cc[v]++;
}
for (int i = 1; i <= n; i++) {
if (cc[i] == 1) {
flag[i] = true;
}
}
for (int i = 1; i <= n; i++) {
if (!flag[i]) {
break;
}
}
for (int i = 1; i <= n; i++) {
if (flag[i]) {
printf ("1\n");
continue;
}
doDp (i, 0);
printf ("%d\n", dp[i]);
}
return 0;
}