Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define F first
- #define S second
- #define mp make_pair
- #define pb push_back
- #define INF 0x3f3f3f3f
- #define LINF 0x3f3f3f3f3f3f3f3fLL
- using namespace std;
- typedef long long ll;
- typedef vector<int> vi;
- typedef set<int> si;
- typedef pair<int,int> ii;
- typedef vector<ii> vii;
- typedef map<string,int> msi;
- typedef map<int,int> mi;
- vector<int> grafo[100010];
- int vis[100010];
- vector<int> peso;
- int x;
- void dfs(int pai){
- x++;
- int ultimo =true;
- for(int i =0;i<grafo[pai].size();i++){
- if(!vis[grafo[pai][i]]){
- ultimo = false;
- vis[grafo[pai][i]] =1;
- dfs(grafo[pai][i]);
- }
- }
- if(ultimo){
- peso.pb(x);
- }
- x--;
- }
- int main(){
- int n;
- scanf("%d",&n);
- for(int i=1;i<n;i++){
- int a,b;
- scanf("%d %d",&a,&b);
- grafo[a].pb(b);
- grafo[b].pb(a);
- }
- x=-1;
- vis[1]=1;
- dfs(1);
- double soma =0;
- for(vector<int>::iterator it=peso.begin();it != peso.end();it++){
- soma+=*it;
- }
- printf("%.14lf",soma/peso.size());
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement