#include<bits/stdc++.h> using namespace std; // #define int long long const int N=1e6+10; int h[N],e[N],ne[N],w[N],idx; void add(int a,int b,int c){ e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } typedef pair<int,int> PII ; bool st[N]; #define x first #define y second int n,k; // int v[N][N]; int bfs(int n){ int res=1; queue<PII>q; q.push({n,0});//存点和到起始点的距离 memset(st, false, sizeof st); st[n]=true; while(!q.empty()){ auto t=q.front() ; // cout<<t.x<<" "<<t.y<<endl; q.pop(); for(int i=h[t.x];~i;i=ne[i]){ int d=w[i],j=e[i]; if(t.y+d <= 2&&st[j]==false){ res++; st[j]=true; q.push({ j ,t.y+d}); } } } return res; } signed main(){ int res=0; memset(h, -1, sizeof h); cin>>n; for(int i=2;i<=n;i++){ int a,b,c;cin>>a>>b; add(i,a,b); add(a,i,b); // cout<<a<<" "<<b<<endl; } for(int i=1;i<=n;i++){ cout<<bfs(i)<<endl;//搜各个点 } // cout<<res; return 0; }
全部评论
(2) 回帖