广搜(其实也可以用换根DP)

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;

const int maxn = 2e5 + 15,tnt = 0x3f3f3f3f;
int n,stamp;
vector<int> vis;
vector<vector<int>> mp;
void bfs(int s){
vector<int> d(n + 5,tnt);
queue<int> q;
stamp++;
q.push(s);
d[s] = 0;
vis[s] = stamp;
while(!q.empty()){
int r = q.front();
q.pop();
for(auto next : mp[r]){
if(vis[next] != stamp){
q.push({next});
vis[next] = stamp;
d[next] = d[r] + 1;
}
}
}
int ans = 0;
for(int i = 1;i <= n;i++){
if(d[i] % 2 == 0 && d[i] != tnt) ans++;
}
cout << ans << " ";
}
int main(){
cin >> n;
mp.resize(n + 5),vis.resize(n + 5,0);
for(int i = 1;i < n;i++){
int x,y;
cin >> x >> y;
mp[x].push_back(y);
mp[y].push_back(x);
}
for(int i = 1;i <= n;i++){
bfs(i);
}

return 0;

}