2 solutions

  • 0
    @ 2024-7-22 13:37:19
    #include<iostream>
    #include<bits/stdc++.h>
    using namespace std;
    const int N = 1100;
    int n;
    vector<int> a[N];
    int dep[N],si[N];
    
    int dfs(int x ,int f)
    {
    	si[x] = 1;
    	dep[x]=dep[f] + 1;
    	for(int i = 0;i < a[x].size() ;i++){
    		if(a[x][i] != f) si[x] += dfs(a[x][i],x);
    	}
    	return si[x];
    }
    int main()
    {
    	int x,y;
    	cin >> n;
    	for(int i = 1 ;i <= n-1 ;i++)
    	{
    		cin >> x >> y;
    		a[x].push_back(y);
    		a[y].push_back(x);
    	}
    	dfs(1,0);
    	for(int i = 1 ;i<=n ;i++) cout << si[i] << " ";
    	return 0;
    }
    
    
    • 0
      @ 2024-7-22 13:36:46
      #include <iostream>
      #include <bits/stdc++.h>
      using namespace std;
      const int  N = 1100;
      int n;
      int K,pre[N],to[N*2],ne[N*2];
      int si[N],dep[N];
      
      void add(int x,int y)
      {
      	to[++K] = y;
      	ne[K] = pre[x];
      	pre[x] = K;
      }
      
      void dfs(int x ,int f)
      {
      	si[x] = 1;
      	dep[x]=dep[f] + 1;
      	for(int i = pre[x];i != 0 ;i = ne[i]){
      		if(to[i]!=f)
      		{
      			dfs(to[i],x);
      			si[x]+=si[to[i]];
      		}
      	}
      }
      int main()
      {
      	int x;
      	int y;
      	cin >> n;
      	for(int i = 1 ;i<=n-1 ;i++)
      	{
      		cin >> x >> y;
      		add(x,y);
      		add(y,x);
      	}
      	dfs(1,0);
      	for(int i = 1 ;i <= n ;i++) cout << si[i] << " ";
      	return 0;
      }
      
      
      • 1

      Information

      ID
      6848
      Time
      1000ms
      Memory
      256MiB
      Difficulty
      10
      Tags
      # Submissions
      7
      Accepted
      3
      Uploaded By