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