mirror of https://github.com/cyp0633/homework.git
53 lines
1.3 KiB
C++
53 lines
1.3 KiB
C++
|
//CF893C Journey
|
|||
|
#include <cstdio>
|
|||
|
#include <iostream>
|
|||
|
using namespace std;
|
|||
|
bool visited[100001];
|
|||
|
int head[100001], nxt[200000], to[200000], n, sons[100001];
|
|||
|
double expectation;
|
|||
|
void dfs(int currentPos, double possibility, int depth);
|
|||
|
void insert(int source, int dest, int i);
|
|||
|
int main()
|
|||
|
{
|
|||
|
scanf("%d", &n);
|
|||
|
int tempSource, tempDest;
|
|||
|
for (int i = 0; i < n - 1; i++)
|
|||
|
{
|
|||
|
scanf("%d %d", &tempSource, &tempDest);
|
|||
|
insert(tempSource, tempDest, i * 2 + 1);
|
|||
|
insert(tempDest, tempSource, i * 2 + 2);
|
|||
|
}
|
|||
|
sons[1] /= 2;
|
|||
|
for (int i = 2; i <= n; i++) //除根节点外,子节点数=连接边数-1
|
|||
|
{
|
|||
|
sons[i] = sons[i] / 2 - 1;
|
|||
|
}
|
|||
|
dfs(1, 1.0, 0);
|
|||
|
printf("%.7lf\n", expectation); //HNU CG强制要求7位小数,不然不过
|
|||
|
}
|
|||
|
void dfs(int currentPos, double possibility, int depth)
|
|||
|
{
|
|||
|
if (visited[currentPos])
|
|||
|
{
|
|||
|
return;
|
|||
|
}
|
|||
|
if (sons[currentPos] == 0)
|
|||
|
{
|
|||
|
expectation += possibility * depth;
|
|||
|
return;
|
|||
|
}
|
|||
|
visited[currentPos] = true;
|
|||
|
double sonPossibility = possibility / sons[currentPos];
|
|||
|
for (int i = head[currentPos]; i != 0; i = nxt[i])
|
|||
|
{
|
|||
|
dfs(to[i], sonPossibility, depth + 1);
|
|||
|
}
|
|||
|
}
|
|||
|
void insert(int source, int dest, int i)
|
|||
|
{
|
|||
|
nxt[i] = head[source];
|
|||
|
to[i] = dest;
|
|||
|
head[source] = i;
|
|||
|
sons[source]++;
|
|||
|
sons[dest]++;
|
|||
|
}
|