牛客练习赛64 B Dis2 树的某个节点的兄弟节点个数

链接：https://ac.nowcoder.com/acm/contest/5633/B
来源：牛客网

题目描述
给出一颗n{n}n个点n−1{n-1}n−1条边的树，点的编号为1,2,…,n−1,n{1,2,…,n-1,n}1,2,…,n−1,n，对于每个点i(1<=i<=n){i(1<=i<=n)}i(1<=i<=n)，输出与点i{i}i距离为2{2}2的点的个数。
两个点的距离定义为两个点最短路径上的边的条数。
输入描述:

第一行一个正整数n{n}n。
接下来n−1{n-1}n−1行每行两个正整数ui,vi{u_i,v_i}ui​,vi​表示点ui,vi{u_i,v_i}ui​,vi​之间有一条边。

输出描述:

输入共n{n}n行，第i{i}i行输出一个整数表示与点i{i}i距离为2{2}2的点的个数。

示例1
输入
复制

4
1 2
2 3
3 4

输出
复制

1
1
1
1

说明

点1,3{1,3}1,3的距离为2{2}2，点2,4{2,4}2,4的距离为2{2}2。

备注:

1<=ui,vi<=n<=200000{1<=u_i,v_i<=n<=200000}1<=ui​,vi​<=n<=200000

很明显对于第 $i$i个点 $V_i$Vi​,他的答案 $ans\left[i\right]$ans[i]等于 $V_i$Vi​的兄弟节点个数

不要 $dfs$dfs
不要 $dfs$dfs
不要 $dfs$dfs

$2e5$2e5的点, $dfs$dfs爆栈了

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif


#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)2e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#endif

#ifndef debug
namespace FIO {
	template <typename T>
	void read(T& x) {
		int f = 1; x = 0;
		char ch = getchar();

		while (ch < '0' || ch > '9') 
			{ if (ch == '-') f = -1; ch = getchar(); }
		while (ch >= '0' && ch <= '9') 
			{ x = x * 10 + ch - '0'; ch = getchar(); }
		x *= f;
	}
};
using namespace FIO;
#endif

int n, m, Q, K;
vector<int> G[MAXN];

//对于点u,兄弟节点个数就是num[i]
//求每一个节点的兄弟节点个数

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	
	read(n);
	int u, v;
	for(int i=1; i<n; i++) {
		read(u), read(v);
		G[u].push_back(v), G[v].push_back(u);
	}
	for(int i=1; i<=n; i++) {
		int cnt = 0; //统计节点i的兄弟节点个数
		for(int k=0; k<(int)G[i].size(); k++) {
			cnt += G[G[i][k]].size() - 1;
		}
		printf("%d\n", cnt);
	}


#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}